[Bug libstdc++/100664] ranges::drop_view fails to meet its complexity requirements

[hewillk at gmail dot com via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100664

--- Comment #2 from 康桓瑋 <hewillk at gmail dot com> ---
(In reply to 康桓瑋 from comment #0)
> 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).
> 

I think _S_needs_cached_begin can be defined as:

  // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
  // both random_access_range and sized_range. Otherwise, cache its result.
  static constexpr bool _S_needs_cached_begin
    = !(__detail::__simple_view<_Vp>
        && random_access_range<const _Vp>
        && sized_range<const _Vp>)
        && !(random_access_range<_Vp> && sized_range<_Vp>);