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.

### 3830. `reverse_view` should not cache when `ranges::next` has constant time complexity

Section: 26.7.20.2 [range.reverse.view] Status: New Submitter: Hewill Kang Opened: 2022-11-14 Last modified: 2022-11-19

Priority: Not Prioritized

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

View all issues with New status.

Discussion:

In order to ensure that `begin` has an amortized constant time, when the underlying range is not a common range, `reverse_view` always caches the result of `ranges::next`.

However, for some non-common ranges, incrementing its `begin` to `end` still guarantees constant time, for example:

>     #include <ranges>
>     #include <vector>
>     #include <list>

>     int main() {
>       std::vector v{42};
>       auto x = std::ranges::subrange(std::counted_iterator(v.begin(), 1), std::default_sentinel)
>              | std::views::reverse;
>       (void) x.begin(); // still caches end iterator in MSVC-STL

>       std::list l{42};
>       auto y = std::ranges::subrange(l.cbegin(), l.end())
>              | std::views::reverse;
>       (void) y.begin(); // still caches end iterator in both libstdc++ and MSVC-STL
>     }

In the above example, although neither `subrange` is a common range, applying `ranges::next` to their iterator-sentinel pairs is still constant time, in this case, there's no need to introduce a cache for `reverse_view` to store the results. We shouldn't pay for things we don't need to use.

Proposed resolution:

This wording is relative to N4917.

1. Modify 26.7.20.2 [range.reverse.view] as indicated:

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

   > > -2- Returns:

   > > >     make_reverse_iterator(ranges::next(ranges::begin(base_), ranges::end(base_)))

   > > -3- Remarks: In order to provide the amortized constant time complexity required by the `range` concept, this function caches the result within the `reverse_view` for use on subsequent calls when both `assignable_from<I&, S>` and `random_access_iterator<I> && sized_sentinel_for<S, I>` are `false`, where `I` is `iterator_t<V>` and `S` is `sentinel_t<V>`.