{"id":2226144,"url":"http://patchwork.ozlabs.org/api/patches/2226144/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.1@forge-stage.sourceware.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/projects/17/?format=json","name":"GNU Compiler Collection","link_name":"gcc","list_id":"gcc-patches.gcc.gnu.org","list_email":"gcc-patches@gcc.gnu.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"","list_archive_url":null,"date":"2026-04-22T10:13:03","name":"[v1,1/1] libstdc++: Fix complexity of drop_view::begin const [PR112641]","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"cc57bc91f87bb82a345456503aa8e02876fdd9ec","submitter":{"id":93215,"url":"http://patchwork.ozlabs.org/api/people/93215/?format=json","name":"ppalka via Sourceware Forge","email":"forge-bot+ppalka@forge-stage.sourceware.org"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuawf4oe6.gcc.gcc-TEST.ppalka.8.1.1@forge-stage.sourceware.org/mbox/","series":[{"id":500958,"url":"http://patchwork.ozlabs.org/api/series/500958/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=500958","date":"2026-04-22T10:13:03","name":"[v1,1/1] libstdc++: Fix complexity of drop_view::begin const [PR112641]","version":1,"mbox":"http://patchwork.ozlabs.org/series/500958/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2226144/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226144/checks/","tags":{},"related":[],"headers":{"Return-Path":"","X-Original-To":["incoming@patchwork.ozlabs.org","gcc-patches@gcc.gnu.org"],"Delivered-To":["patchwork-incoming@legolas.ozlabs.org","gcc-patches@gcc.gnu.org"],"Authentication-Results":["legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)","sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org","sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org","server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39"],"Received":["from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g0w6t2srrz1yCv\n\tfor ; Wed, 22 Apr 2026 20:13:57 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 370F94B9DB59\n\tfor ; Wed, 22 Apr 2026 10:13:55 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id E716F4BA23F4\n for ; Wed, 22 Apr 2026 10:13:28 +0000 (GMT)","from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id B129340546\n for ; Wed, 22 Apr 2026 10:13:28 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 370F94B9DB59","OpenDKIM Filter v2.11.0 sourceware.org E716F4BA23F4"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org E716F4BA23F4","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org E716F4BA23F4","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776852809; cv=none;\n b=M+bPuUQtHMM5fnuvR+scL38xBGl5X3Dolwkignwd3toFn/tHML8IrcQanxOeC7S/PvIvw5sz5D8DyKUSmc63z6C4CKFybCCAUVd4wu92gFXYSm2AgZL4rH34w/DfaI4DwGYsaMyQcOE4FjNIm0jYoX9XtucS4pJrO36qzzW4M3w=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776852809; c=relaxed/simple;\n bh=0FzIYbkYXcV90wxSFVFiP9L7bTgLameIbTM0ltzp59E=;\n h=From:Date:Subject:To:Message-ID;\n b=KQKt1PtsxZYAQqDga3fDbg3Znja0Kfaqve3mRfsvj1VUF04h97JWyOt9a4murBHCgWwHaBY8fxc4ykb+tIZk+onLfs0e/yD8fDZ3SI7lECa5N39VwWNOkRHI8WKh8DfApYEGbdxUD3UI9HjvRPTs/gtcQElss8Va7HVFg9kRjdU=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"ppalka via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 10:13:03 +0000","Subject":"[PATCH v1 1/1] libstdc++: Fix complexity of drop_view::begin const\n [PR112641]","To":"gcc-patches mailing list ","Message-ID":"\n ","X-Mailer":"batrachomyomachia","X-Requested-Reviewer":"redi","X-Pull-Request-Organization":"gcc","X-Pull-Request-Repository":"gcc-TEST","X-Pull-Request":"https://forge.sourceware.org/gcc/gcc-TEST/pulls/8","References":"\n ","In-Reply-To":"\n ","X-Patch-URL":"\n https://forge.sourceware.org/gcc/gcc-TEST/commit/b184fad509fba4941ceb9ec61427a754e677850a","X-BeenThere":"gcc-patches@gcc.gnu.org","X-Mailman-Version":"2.1.30","Precedence":"list","List-Id":"Gcc-patches mailing list ","List-Unsubscribe":",\n ","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n ","Reply-To":"gcc-patches mailing list ,\n ppalka@gcc.gnu.org","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"From: Patrick Palka \n\nViews are required to have a amortized O(1) begin(), but our drop_view's\nconst begin overload is O(n) for non-common ranges. This patch\nreimplements it so that it's O(1) even in that case. See also LWG 4009.\n\n\tPR libstdc++/112641\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/std/ranges (drop_view::begin const): Reimplement\n\tso that it's O(1) instead of O(n) even in the non-common\n\trange case.\n\t* testsuite/std/ranges/adaptors/drop.cc (test10): New test.\n---\n libstdc++-v3/include/std/ranges | 4 ++--\n libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 12 ++++++++++++\n 2 files changed, 14 insertions(+), 2 deletions(-)","diff":"diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges\nindex cebe10683f91..743429dbceae 100644\n--- a/libstdc++-v3/include/std/ranges\n+++ b/libstdc++-v3/include/std/ranges\n@@ -2664,8 +2664,8 @@ namespace views::__adaptor\n begin() const\n \trequires random_access_range && sized_range\n {\n-\treturn ranges::next(ranges::begin(_M_base), _M_count,\n-\t\t\t ranges::end(_M_base));\n+\treturn ranges::begin(_M_base) + ranges::min(ranges::distance(_M_base),\n+\t\t\t\t\t\t _M_count);\n }\n \n constexpr auto\ndiff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc\nindex c9987c61e3c1..0bd5bebb785d 100644\n--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc\n+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc\n@@ -274,6 +274,17 @@ test09()\n static_assert(!requires { views::all | drop; });\n }\n \n+constexpr bool\n+test10()\n+{\n+ // PR libstdc++/112641 - drop_view::begin const may have O(n) complexity\n+ const auto s = ranges::subrange(views::iota(size_t(1)), size_t(-1));\n+ const auto r = ranges::drop_view(s, s.size() - 1);\n+ const auto b = r.begin(); // time out\n+ VERIFY( *b == size_t(-1) );\n+ return true;\n+}\n+\n int\n main()\n {\n@@ -286,4 +297,5 @@ main()\n test07();\n test08();\n test09();\n+ static_assert(test10());\n }\n","prefixes":["v1","1/1"]}