]> git.ipfire.org Git - thirdparty/gcc.git/commit
libstdc++: Fix complexity of drop_view::begin() const [PR112641]
authorPatrick Palka <ppalka@redhat.com>
Tue, 29 Oct 2024 13:26:19 +0000 (09:26 -0400)
committerPatrick Palka <ppalka@redhat.com>
Thu, 9 Jan 2025 22:55:10 +0000 (17:55 -0500)
commit9d650c29562bbb18c1ea5d0064e07f48c177912b
treed9725eb26996bb5f68e3cdbc0ea3ee2345be6288
parent1f509da6d7c9679f727daf539c30f8f1816dd16e
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)
libstdc++-v3/include/std/ranges
libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc