On Fri, Sep 12, 2025 at 7:39 PM Patrick Palka <[email protected]> wrote:
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> Patch generated with -w due to otherwise noisy whitespace changes.
>
> -- >8 --
>
> The ranges::shuffle optimization, copied from std::shuffle, has a
> two-at-a-time PRNG optimization that considers the range of the
> PRNG vs the size of the range. But in C++20 a sentinel is not
> necessarily sized so we can't unconditionally do __last - __first.
>
> We could instead use ranges::size, but that'd take linear time for a
>
Did you mean that we could use ranges::distance here?
> non-sized sentinel which makes the optimization less clear of a win.
> So this patch instead makes us only consider this optimization for
> arguments that model sized_sentinel_for or sized_range.
>
> PR libstdc++/121917
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h (__shuffle_fn::_S_impl): Factor
> out from main operator() overload. Add optional size parameter,
> and only consider the two-at-a-time PRNG optimization if the
> size is given.
> (__shuffle_fn::operator()): Adjust to call _S_impl directly,
> computing the range size for sized_sentinel_for or sized_range
> arguments.
> * testsuite/25_algorithms/shuffle/constrained.cc:
> ---
> libstdc++-v3/include/bits/ranges_algo.h | 35 ++++++++++++++-----
> .../25_algorithms/shuffle/constrained.cc | 18 ++++++++++
> 2 files changed, 44 insertions(+), 9 deletions(-)
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> b/libstdc++-v3/include/bits/ranges_algo.h
> index 6e1e06cb2d0f..855ab1395149 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -1945,12 +1945,10 @@ namespace ranges
>
> struct __shuffle_fn
> {
> - template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
> - typename _Gen>
> - requires permutable<_Iter>
> - && uniform_random_bit_generator<remove_reference_t<_Gen>>
> - _Iter
> - operator()(_Iter __first, _Sent __last, _Gen&& __g) const
> + template<typename _Iter, typename _Sent, typename _Gen>
> + static _Iter
> + _S_impl(_Iter __first, _Sent __last, _Gen&& __g,
> + iter_difference_t<_Iter> __n)
> {
> // FIXME: Correctly handle integer-class difference types.
> if (__first == __last)
> @@ -1964,8 +1962,10 @@ namespace ranges
> using __uc_type
> = common_type_t<typename remove_reference_t<_Gen>::result_type,
> __ud_type>;
>
> + if (__n != -1)
> + {
> const __uc_type __urngrange = __g.max() - __g.min();
> - const __uc_type __urange = __uc_type(__last - __first);
> + const __uc_type __urange = __uc_type(__n);
>
> if (__urngrange / __urange >= __urange)
> // I.e. (__urngrange >= __urange * __urange) but without
> wrap issues.
> @@ -1999,6 +1999,7 @@ namespace ranges
>
> return __i;
> }
> + }
>
> __distr_type __d;
>
> @@ -2009,14 +2010,30 @@ namespace ranges
> return __i;
> }
>
> + template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
> + typename _Gen>
> + requires permutable<_Iter>
> + && uniform_random_bit_generator<remove_reference_t<_Gen>>
> + _Iter
> + operator()(_Iter __first, _Sent __last, _Gen&& __g) const
> + {
> + iter_difference_t<_Iter> __n = -1;
> + if constexpr (sized_sentinel_for<_Sent, _Iter>)
> + __n = __last - __first;
> + return _S_impl(__first, __last, std::forward<_Gen>(__g), __n);
> + }
> +
> template<random_access_range _Range, typename _Gen>
> requires permutable<iterator_t<_Range>>
> && uniform_random_bit_generator<remove_reference_t<_Gen>>
> borrowed_iterator_t<_Range>
> operator()(_Range&& __r, _Gen&& __g) const
> {
> - return (*this)(ranges::begin(__r), ranges::end(__r),
> - std::forward<_Gen>(__g));
> + range_difference_t<_Range> __n = -1;
> + if constexpr (sized_range<_Range>)
> + __n = ranges::size(__r);
> + return _S_impl(ranges::begin(__r), ranges::end(__r),
> + std::forward<_Gen>(__g), __n);
> }
> };
>
> diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
> b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
> index 70c6bdfc3d9e..4d633561508b 100644
> --- a/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
> +++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/constrained.cc
> @@ -86,9 +86,27 @@ test02()
> ranges::shuffle(w, g);
> }
>
> +struct non_default_sentinel_t { };
> +
> +template<std::input_or_output_iterator I>
> +bool operator==(const I& i, non_default_sentinel_t)
> +{ return i == std::default_sentinel; }
> +
> +void
> +test03()
> +{
> + // PR libstdc++/121917 - ranges::shuffle incorrectly requires its
> arguments
> + // to model sized_sentinel_for
> + int a[2]{};
> + std::counted_iterator iter(a, 2);
> + std::default_random_engine e;
> + std::ranges::shuffle(iter, non_default_sentinel_t{}, e);
> +}
> +
> int
> main()
> {
> test01();
> test02();
> + test03();
> }
> --
> 2.51.0.193.g4975ec3473
>
>
