This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of WP status.

### 3482. `drop_view`'s `const begin` should additionally require `sized_range`

Section: 26.7.12.2 [range.drop.view] Status: WP Submitter: Casey Carter Opened: 2020-08-31 Last modified: 2020-11-09

Priority: 0

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

View all issues with WP 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" (26.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 26.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]