Skip to content

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

@CaseyCarter

Description

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    fixedSomething works now, yay!rangesC++20/23 ranges

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions