{"id":2226705,"url":"http://patchwork.ozlabs.org/api/patches/2226705/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.7@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:31","name":"[v1,7/8] libstdc++: Directly implement ranges::sample [PR100795]","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"c77359f9c1d04523ef2b1e17e87f7cf4f3767878","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.7@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/2226705/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226705/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 4g17Pd4zfTz1yHB\n\tfor ; Thu, 23 Apr 2026 04:42:29 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id AD2D840A130E\n\tfor ; Wed, 22 Apr 2026 18:42:27 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 8F72A48FEDB7\n for ; Wed, 22 Apr 2026 18:28:37 +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 490D8434A2\n for ; Wed, 22 Apr 2026 18:28:35 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org AD2D840A130E","OpenDKIM Filter v2.11.0 sourceware.org 8F72A48FEDB7"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org 8F72A48FEDB7","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org 8F72A48FEDB7","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776882517; cv=none;\n b=PilUqfnNLHiP/Zi15mS0R6hH3WmiytKlgtclZPcH+VngpICvctGAkUT806x6NyIr4pRwAeU1bh+yCvaLzFpdwhISDlmsWUfmeJ/Q5ykcwMlDJiRH9J+MkCvP+R2Wqq3pXgotodWOOTI/xaFuzm9KziKESFreTa7cfNl7mfRhnTg=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776882517; c=relaxed/simple;\n bh=v7OwYGZXxVhvzlL+BLSzkhqFkeisPF9kCE3Hep9fcl8=;\n h=From:Date:Subject:To:Message-ID;\n b=M2cDEPwWlrLZtriXzxaeeXEt+ys83ziTL1cETdULXMSVc05C+EorTW3Fpl2wHM7DkW4V5VF4V3GTea1GuQOdDDa5O8A5b9EHGFnKKN2VjeecRQwfGdOr5Bn+13j3c0MeiQj4dKpL4D+DAFtmCJDgwv08EtAJiVrryxUN00Kpcl0=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"ppalka via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 18:27:31 +0000","Subject":"[PATCH v1 7/8] libstdc++: Directly implement ranges::sample\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/ccd7d483f3ecd3c7832772cb18a935dbdca6b4e1","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 (__sample_fn::operator()):\n\tReimplement the forward_iterator branch directly.\n\t* testsuite/25_algorithms/sample/constrained.cc (test02):\n\tNew test.\n---\n libstdc++-v3/include/bits/ranges_algo.h | 70 +++++++++++++++++--\n .../25_algorithms/sample/constrained.cc | 28 ++++++++\n 2 files changed, 91 insertions(+), 7 deletions(-)","diff":"diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex b12da2af1263..672a0ebce0de 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -1839,14 +1839,70 @@ namespace ranges\n operator()(_Iter __first, _Sent __last, _Out __out,\n \t\t iter_difference_t<_Iter> __n, _Gen&& __g) const\n {\n+\t// FIXME: Correctly handle integer-class difference types.\n \tif constexpr (forward_iterator<_Iter>)\n \t {\n-\t // FIXME: Forwarding to std::sample here requires computing __lasti\n-\t // which may take linear time.\n-\t auto __lasti = ranges::next(__first, __last);\n-\t return _GLIBCXX_STD_A::\n-\t sample(std::move(__first), std::move(__lasti), std::move(__out),\n-\t\t __n, std::forward<_Gen>(__g));\n+\t using _Size = iter_difference_t<_Iter>;\n+\t using __distrib_type = uniform_int_distribution<_Size>;\n+\t using __param_type = typename __distrib_type::param_type;\n+\t using _USize = __detail::__make_unsigned_like_t<_Size>;\n+\t using __uc_type\n+\t = common_type_t::result_type, _USize>;\n+\n+\t if (__first == __last)\n+\t return __out;\n+\n+\t __distrib_type __d{};\n+\t _Size __unsampled_sz = ranges::distance(__first, __last);\n+\t __n = std::min(__n, __unsampled_sz);\n+\n+\t // If possible, we use __gen_two_uniform_ints to efficiently produce\n+\t // two random numbers using a single distribution invocation:\n+\n+\t const __uc_type __urngrange = __g.max() - __g.min();\n+\t if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))\n+\t // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without\n+\t // wrapping issues.\n+\t {\n+\t\twhile (__n != 0 && __unsampled_sz >= 2)\n+\t\t {\n+\t\t const pair<_Size, _Size> __p =\n+\t\t __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);\n+\n+\t\t --__unsampled_sz;\n+\t\t if (__p.first < __n)\n+\t\t {\n+\t\t\t*__out = *__first;\n+\t\t\t++__out;\n+\t\t\t--__n;\n+\t\t }\n+\n+\t\t ++__first;\n+\n+\t\t if (__n == 0) break;\n+\n+\t\t --__unsampled_sz;\n+\t\t if (__p.second < __n)\n+\t\t {\n+\t\t\t*__out = *__first;\n+\t\t\t++__out;\n+\t\t\t--__n;\n+\t\t }\n+\n+\t\t ++__first;\n+\t\t }\n+\t }\n+\n+\t // The loop above is otherwise equivalent to this one-at-a-time version:\n+\n+\t for (; __n != 0; ++__first)\n+\t if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)\n+\t\t{\n+\t\t *__out = *__first;\n+\t\t ++__out;\n+\t\t --__n;\n+\t\t}\n+\t return __out;\n \t }\n \telse\n \t {\n@@ -1867,7 +1923,7 @@ namespace ranges\n \t\tif (__k < __n)\n \t\t __out[__k] = *__first;\n \t }\n-\t return __out + __sample_sz;\n+\t return __out + iter_difference_t<_Out>(__sample_sz);\n \t }\n }\n \ndiff --git a/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc\nindex b9945b164903..150e2d2036e0 100644\n--- a/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc\n+++ b/libstdc++-v3/testsuite/25_algorithms/sample/constrained.cc\n@@ -20,6 +20,7 @@\n \n #include \n #include \n+#include \n #include \n #include \n \n@@ -59,9 +60,36 @@ test01()\n }\n }\n \n+void\n+test02()\n+{\n+ // PR libstdc++/100795 - ranges::sample should not use std::sample\n+#if 0 // FIXME: ranges::sample rejects integer-class difference types.\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+#else\n+ auto v = std::views::iota(0, 20);\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::sample(v, w.begin(), 20, rng);\n+ ranges::sort(w);\n+ VERIFY( ranges::equal(w, v) );\n+}\n+\n int\n main()\n {\n test01();\n test01();\n+ test02();\n }\n","prefixes":["v1","7/8"]}