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>.