[Bug libstdc++/112641] New: <ranges>: `drop_view::begin const` has ????(n) complexity

[Bug libstdc++/112641] New: <ranges>: `drop_view::begin const` has ????(n) complexity

[hewillk at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112641

            Bug ID: 112641
           Summary: <ranges>: `drop_view::begin const` has ????(n)
                    complexity
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hewillk at gmail dot com
  Target Milestone: ---

The wording of `drop_view::begin const` in [range.drop.view] is

   Returns: ranges​::​next(ranges​::​begin(base_), count_,
ranges​::​end(base_)).

Note that "returns" is used here, which means that the implementation only
needs to return the value of `ranges::next` and does not need to obtain the
value through `ranges::advance`, which will have 𝒪(n) complexity in the case of
random-access-sized but non-common range.

  #include <ranges>

  int main() {
    const auto s = std::ranges::subrange(std::views::iota(0uz), size_t(-1));
    const auto r = std::ranges::drop_view(s, s.size() - 1);
    const auto b = r.begin(); // time out
  }

https://godbolt.org/z/1KnKKacs8

Thanks to Mr. Jonathan for clarifying this on the LWG mailing list.

[Bug libstdc++/112641] <ranges>: `drop_view::begin const` has O(n) complexity

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112641

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-11-20
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
https://cplusplus.github.io/LWG/issue4009 shows a faster impl for the
random-access && sized case.