{"id":2226712,"url":"http://patchwork.ozlabs.org/api/patches/2226712/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.6@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-22T18:27:30","name":"[v1,6/8] libstdc++: Directly implement ranges::nth_element [PR100795]","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"0fce56554f3501293c747b6fb2084a2108da2377","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.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.6@forge-stage.sourceware.org/mbox/","series":[{"id":501079,"url":"http://patchwork.ozlabs.org/api/series/501079/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=501079","date":"2026-04-22T18:27:24","name":"libstdc++: C++20 iterator awareness fixes for various Ranges algorithms [PR100795]","version":1,"mbox":"http://patchwork.ozlabs.org/series/501079/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2226712/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226712/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=38.145.34.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 [38.145.34.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 4g17W56SgVz1yD5\n\tfor ; Thu, 23 Apr 2026 04:47:13 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id E0F4A4318B55\n\tfor ; Wed, 22 Apr 2026 18:47:11 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id B670448FEC25\n for ; Wed, 22 Apr 2026 18:28:36 +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 3BC78434A1\n for ; Wed, 22 Apr 2026 18:28:35 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org E0F4A4318B55","OpenDKIM Filter v2.11.0 sourceware.org B670448FEC25"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org B670448FEC25","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org B670448FEC25","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776882516; cv=none;\n b=Smyz4ZFbZaRlExuuU40mGLnffIj3oQGKLdy2HA2SOOwoy219P96/Cf1MfpNlfxYDn0AUAkORA2w6sqw+/OZSR4iNlgEJVM7W7Pwak4lEJS43GgzeNrGV1IR2IOn9OpZNdqL7XkNXLTjBHZ5q8whdKrUo87ArrZhuK+dfbpAPsAU=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776882516; c=relaxed/simple;\n bh=A+pko5QOjmtMx1UZzJXI/zdIhJpzZLDwsEhiffb8vec=;\n h=From:Date:Subject:To:Message-ID;\n b=bCb+DZnztKa64n0VZ9uWYWcDeiK4kh109RbfVxtenrija2LjdlmcVfUpuItTLYWrR57cobw9Ys/gPSL35L94RdwMMPCfypujdlWyOPvD+v/gn9k83T+wo3uuc/WxF6bUahtKjCjg0iIRF2XU5LxULzVSqCc0Lq2B/IRIIkZ3W5c=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"ppalka via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 18:27:30 +0000","Subject":"[PATCH v1 6/8] libstdc++: Directly implement ranges::nth_element\n [PR100795]","To":"gcc-patches mailing list ","Message-ID":"\n ","X-Mailer":"batrachomyomachia","X-Pull-Request-Organization":"gcc","X-Pull-Request-Repository":"gcc-TEST","X-Pull-Request":"https://forge.sourceware.org/gcc/gcc-TEST/pulls/57","References":"\n ","In-Reply-To":"\n ","X-Patch-URL":"\n https://forge.sourceware.org/gcc/gcc-TEST/commit/bcc6be79abb3bcb9e14086f033d7c7025245dba0","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\n\tPR libstdc++/100795\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/ranges_algo.h (__detail::__introselect): New,\n\tbased on the stl_algo.h implementation.\n\t(nth_element_fn::operator()): Reimplement in terms of the above.\n\t* testsuite/25_algorithms/nth_element/constrained.cc:\n---\n libstdc++-v3/include/bits/ranges_algo.h | 47 +++++++++++++++++--\n .../25_algorithms/nth_element/constrained.cc | 31 ++++++++++++\n 2 files changed, 73 insertions(+), 5 deletions(-)","diff":"diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex a9924cd9c49e..b12da2af1263 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -2805,6 +2805,33 @@ namespace ranges\n \n inline constexpr __is_sorted_fn is_sorted{};\n \n+ namespace __detail\n+ {\n+ template\n+ constexpr void\n+ __introselect(_Iter __first, _Iter __nth, _Iter __last,\n+\t\t iter_difference_t<_Iter> __depth_limit, _Comp __comp)\n+ {\n+\twhile (__last - __first > 3)\n+\t {\n+\t if (__depth_limit == 0)\n+\t {\n+\t\t__detail::__heap_select(__first, __nth + 1, __last, __comp);\n+\t\t// Place the nth largest element in its final position.\n+\t\tranges::iter_swap(__first, __nth);\n+\t\treturn;\n+\t }\n+\t --__depth_limit;\n+\t _Iter __cut = __detail::__unguarded_partition_pivot(__first, __last, __comp);\n+\t if (__cut <= __nth)\n+\t __first = __cut;\n+\t else\n+\t __last = __cut;\n+\t }\n+\t__detail::__insertion_sort(__first, __last, __comp);\n+ }\n+ } // namespace __detail\n+\n struct __nth_element_fn\n {\n template _Sent,\n@@ -2814,11 +2841,21 @@ namespace ranges\n operator()(_Iter __first, _Iter __nth, _Sent __last,\n \t\t _Comp __comp = {}, _Proj __proj = {}) const\n {\n-\tauto __lasti = ranges::next(__first, __last);\n-\t_GLIBCXX_STD_A::nth_element(std::move(__first), std::move(__nth),\n-\t\t\t\t __lasti,\n-\t\t\t\t __detail::__make_comp_proj(__comp, __proj));\n-\treturn __lasti;\n+\tif constexpr (!same_as<_Iter, _Sent>)\n+\t return (*this)(__first, __nth, ranges::next(__first, __last),\n+\t\t\t std::move(__comp), std::move(__proj));\n+\telse\n+\t {\n+\t if (__first == __last || __nth == __last)\n+\t return __last;\n+\n+\t auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\t auto __n = __detail::__to_unsigned_like(__last - __first);\n+\t __detail::__introselect(__first, __nth, __last,\n+\t\t\t\t std::__bit_width(__n) * 2,\n+\t\t\t\t __comp_proj);\n+\t return __last;\n+\t }\n }\n \n template\n #include \n+#include \n #include \n #include \n \n@@ -67,9 +68,39 @@ test02()\n return x[3] == 4;\n }\n \n+constexpr bool\n+test03()\n+{\n+ // PR libstdc++/100795 - ranges::sort should not use std::sort directly\n+#if __SIZEOF_INT128__\n+ auto v = std::views::iota(__int128(0), __int128(20));\n+#else\n+ auto v = std::views::iota(0ll, 20ll);\n+#endif\n+\n+ int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};\n+ auto w = v | std::views::transform([&](auto i) -> int& { return storage[i]; });\n+ using type = decltype(w);\n+ using cat = std::iterator_traits>::iterator_category;\n+ static_assert( std::same_as );\n+ static_assert( std::ranges::random_access_range );\n+\n+ ranges::nth_element(w, w.begin() + 10);\n+ VERIFY( w[10] == 10 );\n+\n+ ranges::nth_element(w, w.begin() + 5, std::ranges::greater{});\n+ VERIFY( w[5] == 19 - 5 );\n+\n+ ranges::nth_element(w, w.begin() + 15, std::ranges::greater{}, std::negate{});\n+ VERIFY( w[15] == 15 );\n+\n+ return true;\n+}\n+\n int\n main()\n {\n test01();\n static_assert(test02());\n+ static_assert(test03());\n }\n","prefixes":["v1","6/8"]}