Issue 4271: Caching range views claim amortized amortized 𝒪(1) runtime complexity for algorithms that are in fact 𝒪(n)

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

4271. Caching range views claim amortized amortized 𝒪(1) runtime complexity for algorithms that are in fact 𝒪(n)

Section: 24.3.1 [iterator.requirements.general], 25.3.13 [range.approximately.sized], 25.4.1 [range.req.general], 25.4.2 [range.range], 25.4.3 [range.sized], 25.7.8.2 [range.filter.view], 25.7.12.2 [range.drop.view], 25.7.13.2 [range.drop.while.view], 25.7.17.2 [range.split.view], 25.7.21.2 [range.reverse.view], 25.7.30.2 [range.slide.view], 25.7.31.2 [range.chunk.by.view] Status: New Submitter: Andreas Weis Opened: 2025-06-02 Last modified: 2025-06-06

Priority: Not Prioritized

View all other issues in [iterator.requirements.general].

View all issues with New status.

Discussion:

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.

Proposed resolution:

This wording is relative to N5008.

Modify 24.3.1 [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.
Modify 25.3.13 [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 constant~~linear time using ranges::reserve_hint.
Modify 25.4.1 [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.
Modify 25.4.2 [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 constant~~linear time and non-modifying, and
3. (2.3) — […]
Modify 25.4.3 [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 constant~~linear 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) — […]
Modify 25.7.8.2 [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, this~~This function caches the result within the filter_view for use on subsequent calls.
Modify 25.7.12.2 [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, the~~The first overload caches the result within the drop_view for use on subsequent calls.
Modify 25.7.13.2 [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, the~~The first call caches the result within the drop_while_view for use on subsequent calls.
Modify 25.7.17.2 [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, this~~This function caches the result within the split_view for use on subsequent calls.
Modify 25.7.21.2 [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, this~~This function caches the result within the reverse_view for use on subsequent calls.
Modify 25.7.30.2 [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, this~~This 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, this~~This function caches the result within the slide_view for use on subsequent calls when V models slide-caches-first.
Modify 25.7.31.2 [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, this~~This function caches the result within the chunk_by_view for use on subsequent calls.