public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/100621] New: ranges::reverse_view fails to meet its complexity requirements
@ 2021-05-16  5:49 hewillk at gmail dot com
  2021-05-17 10:59 ` [Bug libstdc++/100621] " ppalka at gcc dot gnu.org
                   ` (3 more replies)
  0 siblings, 4 replies; 5+ messages in thread
From: hewillk at gmail dot com @ 2021-05-16  5:49 UTC (permalink / raw)
  To: gcc-bugs

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

            Bug ID: 100621
           Summary: ranges::reverse_view fails to meet its complexity
                    requirements
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hewillk at gmail dot com
  Target Milestone: ---

Hi, in ranges#L3230, the _S_needs_cached_begin of reverse_view is defined as:


  static constexpr bool _S_needs_cached_begin
    = !common_range<_Vp> && !random_access_range<_Vp>;


This definition seems incorrect, consider (https://godbolt.org/z/xfT5E4zK4):


  auto r = std::views::iota(0) | std::views::take(42) | std::views::drop(3);
  using V = decltype(r);
  static_assert(std::ranges::random_access_range<V>);
  static_assert(!std::ranges::common_range<V>);


This r is not a common_range but a random_access_range, so the value of
_S_needs_cached_begin is false, and because the following two asserts fail, the
complexity of ranges::next is O(n):


  using I = decltype(r.begin());
  using S = decltype(r.end());
  static_assert(!std::assignable_from<I&, S>);
  static_assert(!std::sized_sentinel_for<S, I>);

  auto rr = r | std::views::reverse;


This makes rr.begin() fails to meet its complexity requirements in
[range.reverse.view#3]: "Remarks: In order to provide the amortized constant
time complexity required by the range concept, this function caches the result
within the reverse_­view for use on subsequent calls.".

^ permalink raw reply	[flat|nested] 5+ messages in thread
end of thread, other threads:[~2021-10-12 19:08 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-16  5:49 [Bug libstdc++/100621] New: ranges::reverse_view fails to meet its complexity requirements hewillk at gmail dot com
2021-05-17 10:59 ` [Bug libstdc++/100621] " ppalka at gcc dot gnu.org
2021-05-17 11:04 ` ppalka at gcc dot gnu.org
2021-05-18  4:35 ` cvs-commit at gcc dot gnu.org
2021-10-12 19:08 ` ppalka at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).