4009. drop_view::begin const may have 𝒪(n) complexity

Section: 25.7.12.2 [range.drop.view] Status: New Submitter: Hewill Kang Opened: 2023-11-08 Last modified: 2023-11-18

Priority: Not Prioritized

View other active issues in [range.drop.view].

View all other issues in [range.drop.view].

View all issues with New status.

Discussion:

drop_view::begin const is specified to return ranges::next(ranges::begin(base_), count_, ranges::end(base_)), which has 𝒪(n) complexity when base_ is a random-access-sized but non-common range (demo):

#include <ranges>

int main() {
  const auto s = std::ranges::subrange(std::views::iota(0uz), size_t(-1));
  const auto r = std::ranges::drop_view(s, s.size() - 1);
  const auto b = r.begin(); // time out
}

Proposed resolution:

This wording is relative to N4964.

1. Modify 25.7.12.2 [range.drop.view] as indicated:

   constexpr auto begin()
     requires (!(simple-view<V> &&
                 random_access_range<const V> && sized_range<const V>));
   constexpr auto begin() const
     requires random_access_range<const V> && sized_range<const V>;
   

   -3- Returns:

   1. (?.?) — If V models random_access_range and sized_range,

      ranges::begin(base_) + (ranges::distance(base_) - range_difference_t<V>(size()))
      

   2. (?.?) — Otherwise, ranges::next(ranges::begin(base_), count_, ranges::end(base_)).

   -4- Remarks: In order to provide the amortized constant-time complexity required by the range concept when Vdrop_view does not models random_access_range and sized_rangeforward_range, this functionthe first overload caches the result within the drop_view for use on subsequent calls.

   [Note 1: Without this, applying a reverse_view over a drop_view would have quadratic iteration complexity. — end note]

   
   constexpr auto begin() const
     requires random_access_range<const V> && sized_range<const V>;
   

   -?- Returns: ranges::begin(base_) + (ranges::distance(base_) - range_difference_t<const V>(size())).