[gcc r13-9715] libstdc++: Fix complexity of drop_view::begin() const [PR112641]

[Patrick Palka]

https://gcc.gnu.org/g:031e1bf707c9ceb1ec430d41360b6727ad0458db

commit r13-9715-g031e1bf707c9ceb1ec430d41360b6727ad0458db
Author: Patrick Palka <ppalka@redhat.com>
Date:   Tue Oct 29 09:26:19 2024 -0400

    libstdc++: Fix complexity of drop_view::begin() const [PR112641]
    
    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 with a non-sized
    sentinel.  This patch reimplements it so that it's O(1) always.  See
    also LWG 4009.
    
            PR libstdc++/112641
    
    libstdc++-v3/ChangeLog:
    
            * include/std/ranges (drop_view::begin): Reimplement const
            overload so that it's O(1) always.
            * testsuite/std/ranges/adaptors/drop.cc (test10): New test.
    
    Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
    (cherry picked from commit 7f622ee83fbbcf4a4ca70e020db8a0ce4b556b61)

Diff:
---
 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 2735f1613dd1..bdb60ecf7059 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -2530,8 +2530,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 2c4047dbaa38..15827410227a 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
@@ -275,6 +275,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()
 {
@@ -287,4 +298,5 @@ main()
   test07();
   test08();
   test09();
+  static_assert(test10());
 }