Bug 112641 - <ranges>: `drop_view::begin const` has O(n) complexity
Summary: <ranges>: `drop_view::begin const` has O(n) complexity
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 14.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2023-11-20 15:14 UTC by 康桓瑋
Modified: 2024-01-17 11:23 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2023-11-20 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description 康桓瑋 2023-11-20 15:14:47 UTC
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.
Comment 1 Jonathan Wakely 2023-11-20 15:31:19 UTC
https://cplusplus.github.io/LWG/issue4009 shows a faster impl for the random-access && sized case.