4010. subrange::advance should be improved

Section: 26.5.4.3 [range.subrange.access] Status: New Submitter: Hewill Kang Opened: 2023-11-09 Last modified: 2023-11-18 12:05:51 UTC

Priority: Not Prioritized

View all other issues in [range.subrange.access].

View all issues with New status.

Discussion:

subrange::advance always increments begin_ via ranges::advance(begin_, n, end_), which has 𝒪(n) complexity for non-common random-access ranges, which can be improved to 𝒪(1) with the help of the size_ member (if provided).

Proposed resolution:

This wording is relative to N4964.

1. Modify 26.5.4.3 [range.subrange.access] as indicated:

   constexpr subrange& advance(iter_difference_t<I> n);
   

   -9- Effects: Equivalent to:

   if constexpr (bidirectional_iterator<I>) {
     if (n < 0) {
       ranges::advance(begin_, n);
       if constexpr (StoreSize)
         size_ += to-unsigned-like(-n);
       return *this;
     }
   }
   
   auto d = n - ranges::advance(begin_, n, end_);
   if constexpr (StoreSize) {
     n = std::min(n, static_cast<decltype(n)>(size_));
     ranges::advance(begin_, n);
     size_ -= to-unsigned-like(nd);
   } else {
     ranges::advance(begin_, n, end_);
   }
   return *this;