[PATCH 8/8] libstdc++: Directly implement ranges::shuffle [PR100795]

[Jonathan Wakely]

On 26/06/25 22:25 -0400, Patrick Palka wrote:
>	PR libstdc++/100795

OK for trunk.

>
>libstdc++-v3/ChangeLog:
>
>	* include/bits/ranges_algo.h (shuffle_fn::operator()):
>	Reimplement directly.
>	* testsuite/25_algorithms/shuffle/constrained.cc (test02):
>---
> libstdc++-v3/include/bits/ranges_algo.h       | 58 ++++++++++++++++++-
> .../25_algorithms/shuffle/constrained.cc      | 25 ++++++++
> 2 files changed, 80 insertions(+), 3 deletions(-)
>
>diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
>index 672a0ebce0de..83eaa7da28b9 100644
>--- a/libstdc++-v3/include/bits/ranges_algo.h
>+++ b/libstdc++-v3/include/bits/ranges_algo.h
>@@ -1952,9 +1952,61 @@ namespace ranges
>       _Iter
>       operator()(_Iter __first, _Sent __last, _Gen&& __g) const
>       {
>-	auto __lasti = ranges::next(__first, __last);
>-	std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g));
>-	return __lasti;
>+	// FIXME: Correctly handle integer-class difference types.
>+	if (__first == __last)
>+	  return __first;
>+
>+	using _DistanceType = iter_difference_t<_Iter>;
>+	using __ud_type = __detail::__make_unsigned_like_t<_DistanceType>;
>+	using __distr_type = std::uniform_int_distribution<__ud_type>;
>+	using __p_type = typename __distr_type::param_type;
>+
>+	using __uc_type
>+	  = common_type_t<typename remove_reference_t<_Gen>::result_type, __ud_type>;
>+
>+	const __uc_type __urngrange = __g.max() - __g.min();
>+	const __uc_type __urange = __uc_type(__last - __first);
>+
>+	if (__urngrange / __urange >= __urange)
>+	  // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
>+	  {
>+	    _Iter __i = __first + 1;
>+
>+	    // Since we know the range isn't empty, an even number of elements
>+	    // means an uneven number of elements /to swap/, in which case we
>+	    // do the first one up front:
>+
>+	    if ((__urange % 2) == 0)
>+	      {
>+		__distr_type __d{0, 1};
>+		ranges::iter_swap(__i++, __first + __d(__g));
>+	      }
>+
>+	    // Now we know that __last - __i is even, so we do the rest in pairs,
>+	    // using a single distribution invocation to produce swap positions
>+	    // for two successive elements at a time:
>+
>+	    while (__i != __last)
>+	      {
>+		const __uc_type __swap_range = __uc_type(__i - __first) + 1;
>+
>+		const pair<__uc_type, __uc_type> __pospos =
>+		  __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
>+
>+		ranges::iter_swap(__i++, __first + __pospos.first);
>+		ranges::iter_swap(__i++, __first + __pospos.second);
>+	      }
>+
>+	    return __i;
>+	  }
>+
>+	__distr_type __d;
>+
>+	_Iter __i = __first + 1;
>+	for (; __i != __last; ++__i)
>+	  ranges::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
>+
>+	return __i;
>       }
>
>     template<random_access_range _Range, typename _Gen>
>diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
>index d0977a292fee..70c6bdfc3d9e 100644
>--- a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
>+++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
>@@ -20,6 +20,7 @@
>
> #include <algorithm>
> #include <random>
>+#include <ranges>
> #include <vector>
> #include <testsuite_hooks.h>
> #include <testsuite_iterators.h>
>@@ -62,8 +63,32 @@ test01()
>     }
> }
>
>+void
>+test02()
>+{
>+  // PR libstdc++/100795 - ranges::shuffle should not use std::shuffle directly
>+#if 0 // FIXME: ranges::shuffle rejects integer-class difference types.
>+#if __SIZEOF_INT128__
>+  auto v = std::views::iota(__int128(0), __int128(20));
>+#else
>+  auto v = std::views::iota(0ll, 20ll);
>+#endif
>+#else
>+  auto v = std::views::iota(0, 20);
>+#endif
>+
>+  int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};
>+  auto w = v | std::views::transform([&](auto i) -> int& { return storage[i]; });
>+  using type = decltype(w);
>+  static_assert( std::ranges::random_access_range<type> );
>+
>+  std::ranlux48_base g;
>+  ranges::shuffle(w, g);
>+}
>+
> int
> main()
> {
>   test01();
>+  test02();
> }
>-- 
>2.50.0.131.gcf6f63ea6b
>
>