-
Notifications
You must be signed in to change notification settings - Fork 1.6k
Closed
Labels
Description
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).
Reactions are currently unavailable