From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
	id 717E63858C2D; Mon, 20 Nov 2023 15:14:48 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 717E63858C2D
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1700493288;
	bh=+ZCzafntObJvMZn8jXGYXNS82kjGrXqRVeJhsb5GpMU=;
	h=From:To:Subject:Date:From;
	b=g+YC0w55uDv7Pwh1l0F0R1I0ApnwB+aOKOIwqWzQc6wwlXxGzu+UrCbF6hY+mfUi8
	 9f7SsfYFWup37oJii1MN37CHKBeN+E0EaS8BmRPmowhKE9utoZUVgZ7giGzc5Q0Yl6
	 sux/GHDLg5mzb6rNMJMulq/KVjg5+4O3CMby1bjw=
From: "hewillk at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/112641] New: <ranges>: `drop_view::begin const` has
 ????(n) complexity
Date: Mon, 20 Nov 2023 15:14:47 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 14.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: hewillk at gmail dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-112641-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
List-Id: <gcc-bugs.sourceware.org>

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

            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=E2=80=8B::=E2=80=8Bnext(ranges=E2=80=8B::=E2=80=8Bbegin(=
base_), count_,
ranges=E2=80=8B::=E2=80=8Bend(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 =F0=9D=92=AA(n) complexity=
 in the case of
random-access-sized but non-common range.

  #include <ranges>

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

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

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