Title
reverse_view should not cache when ranges::next has constant time complexity
Status
new
Section
[range.reverse.view]
Submitter
Hewill Kang

Created on 2022-11-14.00:00:00 last changed 6 days ago

Messages

Date: 2022-11-30.10:08:16

Proposed resolution:

This wording is relative to N4917.

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

Date: 2022-11-15.00:00:00

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

Date: 2022-11-14.00:00:00

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.

History
Date User Action Args
2022-11-30 10:08:16adminsetmessages: + msg13126
2022-11-19 13:12:11adminsetmessages: + msg13104
2022-11-14 00:00:00admincreate