4010. subrange::advance should be improved

Section: 25.5.4.3 [range.subrange.access] Status: New Submitter: Hewill Kang Opened: 2023-11-09 Last modified: 2024-03-11

Priority: 3

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

[2024-03-11; Reflector poll]

Set priority to 3 after reflector poll.

Jonathan: The "Effects: Equivalent to" wording strongly suggests doing exactly what it suggests there, and the difference would be observable in the number of times the iterator is compared to the sentinel. I'm not sure if we care about that, or if an implementation would be free to make this change as QoI. Regarding the proposed resolution, we know the type of n so we don't need to use decltype(n) in the cast.

Proposed resolution:

This wording is relative to N4964.

1. Modify 25.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;