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

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

Priority: 3

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.

[2022-11-30; Reflector poll]

Set priority to 3 after reflector poll.

"NAD as specified, the Remarks don't need to be precise, they already allow caching to be omitted if not needed. But we could still enable const overloads of begin for cases like these."

"NAD, no need to complicate constraints for such contrived examples. We don't care about random access, sized, non-common ranges like the first case. Any change here should be a paper covering all adaptors, not a piecemeal issue."

Proposed resolution:

This wording is relative to N4917.

1. Modify 25.7.21.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>.