3363. drop_while_view should opt-out of sized_range

Section: 25.7.13.2 [range.drop.while.view] Status: C++20 Submitter: Johel Ernesto Guerrero Peña Opened: 2020-01-07 Last modified: 2021-02-25

Priority: 1

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

View all issues with C++20 status.

Discussion:

If drop_while_view's iterator_t and sentinel_t model forward_iterator and sized_sentinel_for, it will incorrectly satisfy sized_range thanks to the size member function inherited from view_interface.

Because it has to compute its begin(), it can never model sized_range due to not meeting its non-amortized O(1) requirement.

[2020-01-16 Priority set to 1 after discussion on the reflector.]

[2020-02-10; Prague 2020; Casey comments and provides alternative wording]

The fundamental issue here is that both ranges::size and view_interface::size (it should be unsurprising that many of the "default" implementations of member meow in view_interface look just like fallback cases of the ranges::meow CPO) have a case that returns the difference of ranges::end and ranges::begin. If begin and end are amortized* O(1) but not "true" O(1), then the resulting size operation is amortized O(1) and not "true" O(1) as required by the sized_range concept. I don't believe we can or should fix this on a case by case basis, but we should instead relax the complexity requirement for sized_range to be handwavy-amortized O(1).

Previous resolution [SUPERSEDED]:

This wording is relative to N4849.

1. Add the following specialization to 25.2 [ranges.syn]:

   // [drop.while.view], drop while view
     template<view V, class Pred>
       requires input_range<V> && is_object_v<Pred> &&
         indirect_unary_predicate<const Pred, iterator_t<V>>
       class drop_while_view;
   
   
     template<view V, class Pred>
       inline constexpr bool disable_sized_range<drop_while_view<V, Pred>> = true;
   
   
     namespace views { inline constexpr unspecified drop_while = unspecified; }
   

[2020-02 Moved to Immediate on Tuesday in Prague.]

Proposed resolution:

This wording is relative to N4849.

1. Modify 25.4.3 [range.sized] as indicated:

   -2- Given an lvalue t of type remove_reference_t<T>, T models sized_range only if

   1. (2.1) — ranges::size(t) is amortized 𝒪(1), does not modify t, and is equal to ranges::distance(t), and

   2. […]

   -3- [Note: The complexity requirement for the evaluation of ranges::size is non-amortized, unlike the case for the complexity of the evaluations of ranges::begin and ranges::end in the range concept. — end note]