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

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

Priority: 3

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.

[2022-11-30; Reflector poll]

Set priority to 3 after reflector poll.

"NAD, these examples seem entirely contrived. If not NAD, don't need the common_range check if we are checking that the sentinel models input_iterator."

Proposed resolution:

This wording is relative to N4917.

1. Modify 25.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_));
         }
       }
       […]
     };
     […]
   }