Title
subrange::advance should be improved
Status
new
Section
[range.subrange.access]
Submitter
Hewill Kang

Created on 2023-11-09.00:00:00 last changed 4 months ago

Messages

Date: 2024-03-11.21:55:38

Proposed resolution:

This wording is relative to N4964.

  1. Modify [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;
    
Date: 2024-03-15.00:00:00

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

Date: 2023-11-09.00:00:00

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

History
Date User Action Args
2024-03-11 21:55:38adminsetmessages: + msg13983
2023-11-18 12:05:51adminsetmessages: + msg13861
2023-11-09 00:00:00admincreate