https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100664
Bug ID: 100664
Summary: ranges::drop_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#L2043, the _S_needs_cached_begin of reverse_view is defined as:
static constexpr bool _S_needs_cached_begin
= !(random_access_range<const _Vp> && sized_range<const _Vp>);
I think this definition is insufficient, because there may be a non-simple_view
V that can satisfy random_access_range<const _Vp> && sized_range<const _Vp> but
not random_access_range<_Vp> && sized_range<_Vp>, in this case, the complexity
of ranges::next would be O(n).
There is no such view in the standard library, but it can be easily
implemented:
(https://godbolt.org/z/oxY4e77br)
template <view V>
struct common_non_const_view : view_interface<common_non_const_view<V>> {
private:
using I = iterator_t<V>;
using S = sentinel_t<V>;
V base_ = V();
public:
common_non_const_view() = default;
constexpr common_non_const_view(V base) : base_(std::move(base)) {}
constexpr auto begin()
{ return std::common_iterator<I, S>{ranges::begin(base_)}; }
constexpr auto begin() const requires ranges::range<const V>
{ return std::ranges::begin(base_); }
constexpr auto end()
{ return std::common_iterator<I, S>{ranges::end(base_)}; }
constexpr auto end() const requires ranges::range<const V>
{ return ranges::end(base_); }
constexpr auto size() requires sized_range<V>
{ return ranges::size(base_); }
constexpr auto size() const requires sized_range<const V>
{ return ranges::size(base_); }
};
subrange sub(std::counted_iterator(views::iota(0).begin(), 42),
std::default_sentinel);
const common_non_const_view cr{sub};
static_assert(random_access_range<decltype(cr)>);
static_assert(sized_range<decltype(cr)>);
common_non_const_view r{sub};
static_assert(!random_access_range<decltype(r)>);
static_assert(forward_range<decltype(r)>);
static_assert(sized_range<decltype(r)>);
The above *const* common_non_const_view models random_access_range and
sized_range, but the non-const one only models sized_range. Since it also
models forward_range, we still need to cache the results of ranges::next() in
the begin() of drop_view, just as says in [[range.drop#view-4]]:
auto drop = r | std::views::drop(41);
static_assert(forward_range<decltype(drop)>);
auto it = drop.begin(); // need cached
