<ranges>: stride_view::iterator::operator+= could have O(N) complexity

[CaseyCarter]

If the iterator and sentinel types of the underlying view type don't model sized_sentinel_for, the ranges::advance call depicted in the "Effects: Equivalent to" code:

if (n > 0) {
  missing_ = ranges::advance(current_, stride_ * n, end_);
}

has O(n) complexity. However, all operations on conforming random-access iterators must have O(1) complexity. This can perhaps be fixed by advancing the iterator in two steps:

if (n > 0) {
  current_ += stride_ * (n - 1);
  missing_ = ranges::advance(current_, stride_, end_);
}

Which has complexity O(stride_). (Admittedly icky, especially when stride_ is near n.)

Alternatively, we could additionally require sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>> for iterator to model random_access, which would ensure that the problematic advance call is O(1).

[CaseyCarter]

@tcanens @cjdb ^^^

[timsong-cpp]

The first fix sounds good to me (and we'll need to fix this for chunk too).

I don't think the O(stride_) complexity is a problem - that's no different from operator++.

[CaseyCarter]

LWG isn't really equipped to track issues in things that don't appear yet in a working draft.

[hewillk]

LWG isn't really equipped to track issues in things that don't appear yet in a working draft.

Maybe now is the time to submit an LWG?
This is LWG 3880.