https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100621
Bug ID: 100621
Summary: ranges::reverse_view fails to meet its complexity
requirements
Product: gcc
Version: 12.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: hewillk at gmail dot com
Target Milestone: ---
Hi, in ranges#L3230, the _S_needs_cached_begin of reverse_view is defined as:
static constexpr bool _S_needs_cached_begin
= !common_range<_Vp> && !random_access_range<_Vp>;
This definition seems incorrect, consider (https://godbolt.org/z/xfT5E4zK4):
auto r = std::views::iota(0) | std::views::take(42) | std::views::drop(3);
using V = decltype(r);
static_assert(std::ranges::random_access_range<V>);
static_assert(!std::ranges::common_range<V>);
This r is not a common_range but a random_access_range, so the value of
_S_needs_cached_begin is false, and because the following two asserts fail, the
complexity of ranges::next is O(n):
using I = decltype(r.begin());
using S = decltype(r.end());
static_assert(!std::assignable_from<I&, S>);
static_assert(!std::sized_sentinel_for<S, I>);
auto rr = r | std::views::reverse;
This makes rr.begin() fails to meet its complexity requirements in
[range.reverse.view#3]: "Remarks: In order to provide the amortized constant
time complexity required by the range concept, this function caches the result
within the reverse_view for use on subsequent calls.".
