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