3482. drop_view's const begin should additionally require sized_range

Section: 25.7.12.2 [range.drop.view] Status: C++23 Submitter: Casey Carter Opened: 2020-08-31 Last modified: 2023-11-22

Priority: 0

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

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

View all issues with C++23 status.

Discussion:

When the underlying range models both random_access_range and sized_range, a drop_view can easily calculate its first iterator in 𝒪(1) as by the underlying range's first iterator plus the minimum of the number of elements to drop and the size of the underlying range. In this case drop_view::begin need not "cache the result within the drop_view for use on subsequent calls" "in order to provide the amortized constant-time complexity required by the range concept" (25.7.12.2 [range.drop.view]/4). However, drop_view::begin() const does not require sized_range, it requires only random_access_range. There's no way to implementing what amounts to a requirement that calls to begin after the first must be 𝒪(1) without memoization.

Performing memoization in a const member function in a manner consistent with 16.4.6.10 [res.on.data.races] is impossible without some kind of thread synchronization. It is not the intended design for anything in current Range library to require such implementation heroics, we typically fall back to mutable-only iteration to avoid thread synchronization concerns. (Note that both range-v3 and cmcstl2 handle drop_view::begin() const incorrectly by performing 𝒪(N) lookup of the first iterator on each call to begin, which is consistent with 16.4.6.10 [res.on.data.races] but fails to meet the complexity requirements imposed by the range concept.) We should fall back to mutable-only iteration here as well when the underlying range is not a sized_range.

For drop_view, changing the constraints on the const overload of begin also requires changing the constraints on the non-const overload. The non-const begin tries to constrain itself out of overload resolution when the const overload would be valid if the underlying range models the exposition-only simple-view concept. (Recall that T models simple-view iff T models view, const T models range, and T and const T have the same iterator and sentinel types.) Effectively this means the constraints on the non-const overload must require either that the underlying range fails to model simple-view or that the constraints on the const overload would not be satisfied. So when we add a new sized_range requirement to the const overload, we must also add its negation to the mutable overload. (The current form of the constraint on the mutable begin overload is !(simple-view<V> && random_access_range<V>) instead of !(simple-view<V> && random_access_range<const V>) because of an unstated premise that V and const V should both have the same category when both are ranges. Avoiding this unstated premise would make it easier for future readers to grasp what's happening here; we should formulate our new constraints in terms of const V instead of V.)

[2020-09-29; Reflector discussions]

Status to Tentatively Ready and priority to 0 after five positive votes on the reflector.

[2020-11-09 Approved In November virtual meeting. Status changed: Tentatively Ready → WP.]

Proposed resolution:

This wording is relative to N4861.

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

   namespace std::ranges {
     template<view V>
     class drop_view : public view_interface<drop_view<V>> {
     public:
       […]
       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>;    
       […]
     };
   }
   

   […]

   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: 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 drop_view models forward_range, the first overload caches the result within the drop_view for use on subsequent calls. [Note: Without this, applying a reverse_view over a drop_view would have quadratic iteration complexity. — end note]