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.

### 3829. `as_rvalue_view::end` should improve non-common case

Section: 26.7.7.2 [range.as.rvalue.view] Status: New Submitter: Hewill Kang Opened: 2022-11-13 Last modified: 2022-11-19

Priority: Not Prioritized

View all issues with New status.

Discussion:

Currently, when the underlying range is not a common range, `as_rvalue_view::begin` and `end` return `move_iterator` and `move_sentinel` respectively, this seems reasonable since `move_sentinel` is a sentinel adaptor introduced by C++20 specifically for comparison with `move_iterator`.

However, in the case where the sentinel type of the underlying type is an input iterator, this may lead to some performance issues, consider:

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

>     int main() {
>       std::list<std::tuple<int&>> l;
>       auto k = std::move(l) | std::views::keys;
>       auto s = std::ranges::subrange(std::cbegin(k), std::end(k));
>       (void) std::ranges::next(s.begin(), s.end()); // constant time
>       auto r = s | std::views::as_rvalue;
>       (void) std::ranges::next(r.begin(), r.end()); // linear time
>     }

The above `subrange` is constructed by the `elements_view::iterator<true>` and `elements_view::iterator<false>` pair, and since the former can be assigned by the latter, when we use `ranges::next` to increment the `begin` of `s` to its `end`, the `assignable_from` branch will be executed, so we get a constant-time complexity.

However, when we apply `views::as_rvalue` to `s`, the `as_rvalue_view::end` will go into the non-common branch and return `move_sentinel`. And because `move_iterator` cannot be assigned by `move_sentinel`, `ranges::next` will successively increment the `begin` of `s` until its end, we get the linear-time complexity this time.

I think it is more appropriate to return `move_iterator` for the above case, as this preserves the assignability, but also preserves the iterator operability that the original sentinel type has.

Another benefit of doing this is that when the sentinel type of underlying range can be subtracted from its iterator type but does not model `sized_sentinel_for`, returning different `move_iterator` makes them still subtractable, because its `operator-` only constrain the `x.base() - y.base()` being well-formed.

This also solves the issue of `as_rvalue_view` being a valid type but does not model a `range` in some cases, for example:

>     #include <ranges>

>     int main() {
>       std::move_iterator<int*> i;
>       std::move_iterator<const int*> ci;
>       std::ranges::subrange s(i, ci);
>       std::ranges::as_rvalue_view r(s); // not failed
>       static_assert(std::ranges::range<decltype(r)>); // failed
>     }

This is because currently, `as_rvalue_view` does not explicitly specify the template parameters of the returned `move_iterator` and `move_sentinel`, so based on CTAD, its `begin` will return `move_iterator(move_iterator(...))` which is still `move_iterator<int*>`, and its `end` will return `move_sentinel<move_iterator<const int*>>`. Those two types are not comparable, so `r` does not constitute a valid `range`.

The proposed resolution is to return `move_iterator` when the sentinel type of the underlying range models `input_iterator`.

Proposed resolution:

This wording is relative to N4917.

1. Modify 26.7.7.2 [range.as.rvalue.view] as indicated:

   >     namespace std::ranges {
   >       template<view V>
   >         requires input_range<V>
   >       class as_rvalue_view : public view_interface<as_rvalue_view<V>> {
   >         […]
   >         constexpr auto begin() requires (!simple-view<V>)
   >         { return move_iterator(ranges::begin(base_)); }
   >         constexpr auto begin() const requires range<const V>
   >         { return move_iterator(ranges::begin(base_)); }

   >         constexpr auto end() requires (!simple-view<V>) {
   >           if constexpr (common_range<V> || input_iterator<sentinel_t<V>>) {
   >             return move_iterator(ranges::end(base_));
   >           } else {
   >             return move_sentinel(ranges::end(base_));
   >           }
   >         }
   >         constexpr auto end() const requires range<const V> {
   >           if constexpr (common_range<const V> || input_iterator<sentinel_t<const V>>) {
   >             return move_iterator(ranges::end(base_));
   >           } else {
   >             return move_sentinel(ranges::end(base_));
   >           }
   >         }
   >         […]
   >       };
   >       […]
   >     }