On Fri, 25 Oct 2024 at 16:24, Patrick Palka <ppa...@redhat.com> wrote: > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk/backports?
OK for all (also approved on the forge). > Also available in PR form at https://forge.sourceware.org/gcc/gcc-TEST/pulls/8 > > -- >8 -- > > Views are required to have a amortized O(1) begin(), but our drop_view's > const begin overload is O(n) for non-common ranges. This patch > reimplements it so that it's O(1) even in that case. See also LWG 4009. > > PR libstdc++/112641 > > libstdc++-v3/ChangeLog: > > * include/std/ranges (drop_view::begin const): Reimplement > so that it's O(1) instead of O(n) even in the non-common > range case. > * testsuite/std/ranges/adaptors/drop.cc (test10): New test. > --- > libstdc++-v3/include/std/ranges | 4 ++-- > libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 12 ++++++++++++ > 2 files changed, 14 insertions(+), 2 deletions(-) > > diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges > index cebe10683f9..743429dbcea 100644 > --- a/libstdc++-v3/include/std/ranges > +++ b/libstdc++-v3/include/std/ranges > @@ -2664,8 +2664,8 @@ namespace views::__adaptor > begin() const > requires random_access_range<const _Vp> && sized_range<const _Vp> > { > - return ranges::next(ranges::begin(_M_base), _M_count, > - ranges::end(_M_base)); > + return ranges::begin(_M_base) + ranges::min(ranges::distance(_M_base), > + _M_count); > } > > constexpr auto > diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc > b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc > index c9987c61e3c..0bd5bebb785 100644 > --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc > +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc > @@ -274,6 +274,17 @@ test09() > static_assert(!requires { views::all | drop; }); > } > > +constexpr bool > +test10() > +{ > + // PR libstdc++/112641 - drop_view::begin const may have O(n) complexity > + const auto s = ranges::subrange(views::iota(size_t(1)), size_t(-1)); > + const auto r = ranges::drop_view(s, s.size() - 1); > + const auto b = r.begin(); // time out > + VERIFY( *b == size_t(-1) ); > + return true; > +} > + > int > main() > { > @@ -286,4 +297,5 @@ main() > test07(); > test08(); > test09(); > + static_assert(test10()); > } > -- > 2.47.0.118.gfd3785337b >
