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.

3363. drop_while_view should opt-out of sized_range

Section: 24.7.9.2 [range.drop.while.view] Status: WP Submitter: Johel Ernesto Guerrero Peña Opened: 2020-01-07 Last modified: 2020-02-24

Priority: 1

View all issues with WP 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 24.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 24.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]