diff options
| author | Patrick Palka <ppalka@redhat.com> | 2024-10-29 09:26:19 -0400 |
|---|---|---|
| committer | Patrick Palka <ppalka@redhat.com> | 2024-10-29 09:26:19 -0400 |
| commit | 7f622ee83fbbcf4a4ca70e020db8a0ce4b556b61 (patch) | |
| tree | a40dbea2b0dd6885d4d4a8fc0a72587e207ce037 /libstdc++-v3 | |
| parent | 7f41203f08b9948c1c636dc9d66571121c6c7793 (diff) | |
| download | gcc-7f622ee83fbbcf4a4ca70e020db8a0ce4b556b61.zip gcc-7f622ee83fbbcf4a4ca70e020db8a0ce4b556b61.tar.gz gcc-7f622ee83fbbcf4a4ca70e020db8a0ce4b556b61.tar.bz2 | |
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>
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/include/std/ranges | 4 | ||||
| -rw-r--r-- | 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 cebe106..743429d 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 c9987c6..0bd5beb 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()); } |