Proposed resolution:

This wording is relative to N5008.

1. Modify [iterator.requirements.general] as indicated:

   -14- All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized)linear time. Therefore, requirement tables and concept definitions for the iterators do not specify complexity.

2. Modify [range.approximately.sized] as indicated:

   -1- The `approximately_sized_range` concept refines range with the requirement that an approximation of the number of elements in the range can be determined in amortized constantlinear time using `ranges::reserve_hint`.

3. Modify [range.req.general] as indicated:

   -2- The `range` concept requires that `ranges::begin` and `ranges::end` return an iterator and a sentinel, respectively. The `sized_range` concept refines range with the requirement that `ranges::size` be amortized 𝒪(1n). The `view` concept specifies requirements on a `range` type to provide operations with predictable complexity.

4. Modify [range.range] as indicated:

   -2- Given an expression `t` such that `decltype((t))` is T&, `T` models `range` only if

   1. (2.1) — […]

   2. (2.2) — both `ranges::begin(t)` and `ranges::end(t)` are amortized constantlinear time and non-modifying, and

   3. (2.3) — […]

5. Modify [range.sized] as indicated:

   -1- The `sized_range` concept refines `approximately_sized_range` with the requirement that the number of elements in the range can be determined in amortized constantlinear time using `ranges::size`.

   template<class T>
     concept sized_range =
       approximately_sized_range<T> && requires(T& t) { ranges::size(t); };
   

   -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 𝒪(1n), does not modify `t`, and is equal to `ranges::distance(ranges::begin(t), ranges::end(t))`, and

   2. (2.2) — […]

6. Modify [range.filter.view] as indicated:

   constexpr iterator begin();
   

   -3- Preconditions: […]

   -4- Returns: […]

   -5- Remarks: In order to provide the amortized constant time complexity required by the `range` concept when `filter_view` models `forward_range`, thisThis function caches the result within the `filter_view` for use on subsequent calls.

7. Modify [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: […]

   -4- Remarks: In order to provide the amortized constant-time complexity required by the `range` concept when `drop_view` models `forward_range`, theThe first overload caches the result within the `drop_view` for use on subsequent calls.

8. Modify [range.drop.while.view] as indicated:

   constexpr auto begin();
   

   -3- Preconditions: […]

   -4- Returns: […]

   -5- Remarks: In order to provide the amortized constant-time complexity required by the `range` concept when `drop_while_view` models `forward_range`, theThe first call caches the result within the `drop_while_view` for use on subsequent calls.

9. Modify [range.split.view] as indicated:

   constexpr iterator begin();
   

   -3- Returns: […]

   -4- Remarks: In order to provide the amortized constant time complexity required by the `range` concept, thisThis function caches the result within the `split_view` for use on subsequent calls.

10. Modify [range.reverse.view] as indicated:

    constexpr reverse_iterator<iterator_t<V>> begin();
    

    -2- Returns: […]

    -3- Remarks: In order to provide the amortized constant time complexity required by the `range` concept, thisThis function caches the result within the `reverse_view` for use on subsequent calls.

11. Modify [range.slide.view] as indicated:

    constexpr auto begin()
      requires (!(simple-view<V> && slide-caches-nothing<const V>));
    

    -3- Returns: […]

    -4- Remarks: In order to provide the amortized constant-time complexity required by the `range` concept, thisThis function caches the result within the `slide_view` for use on subsequent calls when `V` models slide-caches-first.

    […]

    constexpr auto end()
      requires (!(simple-view<V> && slide-caches-nothing<const V>));
    

    -6- Returns: […]

    -7- Remarks: In order to provide the amortized constant-time complexity required by the `range` concept, thisThis function caches the result within the `slide_view` for use on subsequent calls when `V` models slide-caches-first.

12. Modify [range.chunk.by.view] as indicated:

    constexpr iterator begin();
    

    -3- Preconditions: […]

    -4- Returns: […]

    -5- Remarks: In order to provide the amortized constant-time complexity required by the `range` concept, thisThis function caches the result within the `chunk_by_view` for use on subsequent calls.

Currently range views that cache the result of their operation claim an amortized 𝒪(1) worst-case runtime complexity. This is inconsistent with the established practice in algorithm analysis, where the given complexity bound must hold for all possible sequences of operations. Caching is not sufficient to lower the complexity bound here, as the sequence that contains only a single call to the operation will cause a runtime cost linear in the size of the underlying range. Thus all of the caching range operations are in fact 𝒪(n).

Apart from the caching view operations, this also has secondary impacts in other places that rely on the complexity of iterator functions, such as the iterator requirements and functions for computing the size of a range.

It is unclear how desirable it is under these circumstances to continue disallowing other kinds of 𝒪(n) behavior for iterator functions. While caching offers clear benefits in the context of lazy evaluation, it cannot prevent losing the 𝒪(1) complexity guarantee. The proposed changes below therefore do not address the issue that other types of views (such as hypothetical non-caching variants of the affected views) that were previously considered invalid will become valid with these changes.