libstdc++: Fix ranges::shuffle for non-sized range [PR121917]

  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
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(-)
  

On Fri, 12 Sept 2025 at 18:39, Patrick Palka <ppalka@redhat.com> 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
> 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)

This _S_impl should be private, however ...

>        {
>         // 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)

Having this as a runtime check for != 1 seems a little inelegant when
we've already determined statically whether we want to consider the
optimization.

We could leave the main implementation in the operator()(Iter, Sent,
Gen&&) overload and just add:

if constexpr (sized_sentinel_for<Sent, Iter>)

here instead of 'if ( n != 1)'

Then in the operator()(R&&, Gen&&) overload do:

    if constexpr (sized_range<_Range>)
      {
        auto __first = ranges::begin(__r);
        return (*this)(__first, __first + ranges::size(__r),
               std::forward<_Gen>(__g));
      }
    else
      return (*this)(ranges::begin(__r), ranges::end(__r),
             std::forward<_Gen>(__g));

This way we don't need to pass n to _S_impl, we just ensure that we
pass a sized sentinel instead, and that enables the optimization.
  

On Fri, 12 Sep 2025, Jonathan Wakely wrote:

> On Fri, 12 Sept 2025 at 18:39, Patrick Palka <ppalka@redhat.com> 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
> > 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)
> 
> This _S_impl should be private, however ...
> 
> >        {
> >         // 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)
> 
> Having this as a runtime check for != 1 seems a little inelegant when
> we've already determined statically whether we want to consider the
> optimization.
> 
> We could leave the main implementation in the operator()(Iter, Sent,
> Gen&&) overload and just add:
> 
> if constexpr (sized_sentinel_for<Sent, Iter>)
> 
> here instead of 'if ( n != 1)'
> 
> Then in the operator()(R&&, Gen&&) overload do:
> 
>     if constexpr (sized_range<_Range>)
>       {
>         auto __first = ranges::begin(__r);
>         return (*this)(__first, __first + ranges::size(__r),
>                std::forward<_Gen>(__g));
>       }
>     else
>       return (*this)(ranges::begin(__r), ranges::end(__r),
>              std::forward<_Gen>(__g));
> 
> This way we don't need to pass n to _S_impl, we just ensure that we
> pass a sized sentinel instead, and that enables the optimization.

Sounds good, like so?

-- >8 --

Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]

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
non-sized sentinel which makes the optimization less clear of a win.
So this patch instead makes us only consider this optimization for
sized ranges.

	PR libstdc++/121917

libstdc++-v3/ChangeLog:

	* include/bits/ranges_algo.h (__shuffle_fn::operator()): Only
	consider the two-at-a-time PRNG optimization if the range is
	sized.
	* testsuite/25_algorithms/shuffle/constrained.cc (test03): New
	test.
---
 libstdc++-v3/include/bits/ranges_algo.h        |  8 ++++++++
 .../25_algorithms/shuffle/constrained.cc       | 18 ++++++++++++++++++
 2 files changed, 26 insertions(+)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 6e1e06cb2d0f..911ef90b971a 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1967,6 +1967,7 @@ namespace ranges
 	const __uc_type __urngrange = __g.max() - __g.min();
 	const __uc_type __urange = __uc_type(__last - __first);
 
+	if constexpr (sized_sentinel_for<__Sent, _Iter>)
 	  if (__urngrange / __urange >= __urange)
 	    // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
 	    {
@@ -2015,6 +2016,13 @@ namespace ranges
       borrowed_iterator_t<_Range>
       operator()(_Range&& __r, _Gen&& __g) const
       {
+	if constexpr (sized_range<_Range>
+		      && !sized_sentinel_for<sentinel_t<_Range>,
+					     iterator_t<_Range>)
+	  return (*this)(ranges::begin(__r),
+			 ranges::begin(__r) + ranges::size(__r),
+			 std::forward<_Gen>(__g));
+	else
 	  return (*this)(ranges::begin(__r), ranges::end(__r),
 			 std::forward<_Gen>(__g));
       }
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();
 }
  

On Fri, 12 Sep 2025, Patrick Palka wrote:

> On Fri, 12 Sep 2025, Jonathan Wakely wrote:
> 
> > On Fri, 12 Sept 2025 at 18:39, Patrick Palka <ppalka@redhat.com> 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
> > > 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)
> > 
> > This _S_impl should be private, however ...
> > 
> > >        {
> > >         // 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)
> > 
> > Having this as a runtime check for != 1 seems a little inelegant when
> > we've already determined statically whether we want to consider the
> > optimization.
> > 
> > We could leave the main implementation in the operator()(Iter, Sent,
> > Gen&&) overload and just add:
> > 
> > if constexpr (sized_sentinel_for<Sent, Iter>)
> > 
> > here instead of 'if ( n != 1)'
> > 
> > Then in the operator()(R&&, Gen&&) overload do:
> > 
> >     if constexpr (sized_range<_Range>)
> >       {
> >         auto __first = ranges::begin(__r);
> >         return (*this)(__first, __first + ranges::size(__r),
> >                std::forward<_Gen>(__g));
> >       }
> >     else
> >       return (*this)(ranges::begin(__r), ranges::end(__r),
> >              std::forward<_Gen>(__g));
> > 
> > This way we don't need to pass n to _S_impl, we just ensure that we
> > pass a sized sentinel instead, and that enables the optimization.
> 
> Sounds good, like so?
> 
> -- >8 --
> 
> Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
> 
> 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
> non-sized sentinel which makes the optimization less clear of a win.
> So this patch instead makes us only consider this optimization for
> sized ranges.
> 
> 	PR libstdc++/121917
> 
> libstdc++-v3/ChangeLog:
> 
> 	* include/bits/ranges_algo.h (__shuffle_fn::operator()): Only
> 	consider the two-at-a-time PRNG optimization if the range is
> 	sized.
> 	* testsuite/25_algorithms/shuffle/constrained.cc (test03): New
> 	test.

Whoops, forgot to --amend the commit.  This is the correct diff:

-- >8 --

Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]

---
 libstdc++-v3/include/bits/ranges_algo.h        | 11 ++++++++++-
 .../25_algorithms/shuffle/constrained.cc       | 18 ++++++++++++++++++
 2 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 6e1e06cb2d0f..f886edbb952c 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1964,9 +1964,10 @@ namespace ranges
 	using __uc_type
 	  = common_type_t<typename remove_reference_t<_Gen>::result_type, __ud_type>;
 
+	if constexpr (sized_sentinel_for<_Sent, _Iter>)
+	  {
 	    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.
 	      {
@@ -1999,6 +2000,7 @@ namespace ranges
 
 		return __i;
 	      }
+	  }
 
 	__distr_type __d;
 
@@ -2015,6 +2017,13 @@ namespace ranges
       borrowed_iterator_t<_Range>
       operator()(_Range&& __r, _Gen&& __g) const
       {
+	if constexpr (sized_range<_Range>
+		      && !sized_sentinel_for<sentinel_t<_Range>,
+					     iterator_t<_Range>>)
+	  return (*this)(ranges::begin(__r),
+			 ranges::begin(__r) + ranges::size(__r),
+			 std::forward<_Gen>(__g));
+	else
 	  return (*this)(ranges::begin(__r), ranges::end(__r),
 			 std::forward<_Gen>(__g));
       }
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();
 }
  

On Fri, 12 Sept 2025 at 21:57, Patrick Palka wrote:
>
> On Fri, 12 Sep 2025, Patrick Palka wrote:
>
> > On Fri, 12 Sep 2025, Jonathan Wakely wrote:
> >
> > > On Fri, 12 Sept 2025 at 18:39, Patrick Palka <ppalka@redhat.com> 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
> > > > 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)
> > >
> > > This _S_impl should be private, however ...
> > >
> > > >        {
> > > >         // 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)
> > >
> > > Having this as a runtime check for != 1 seems a little inelegant when
> > > we've already determined statically whether we want to consider the
> > > optimization.
> > >
> > > We could leave the main implementation in the operator()(Iter, Sent,
> > > Gen&&) overload and just add:
> > >
> > > if constexpr (sized_sentinel_for<Sent, Iter>)
> > >
> > > here instead of 'if ( n != 1)'
> > >
> > > Then in the operator()(R&&, Gen&&) overload do:
> > >
> > >     if constexpr (sized_range<_Range>)
> > >       {
> > >         auto __first = ranges::begin(__r);
> > >         return (*this)(__first, __first + ranges::size(__r),
> > >                std::forward<_Gen>(__g));
> > >       }
> > >     else
> > >       return (*this)(ranges::begin(__r), ranges::end(__r),
> > >              std::forward<_Gen>(__g));
> > >
> > > This way we don't need to pass n to _S_impl, we just ensure that we
> > > pass a sized sentinel instead, and that enables the optimization.
> >
> > Sounds good, like so?
> >
> > -- >8 --
> >
> > Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
> >
> > 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
> > non-sized sentinel which makes the optimization less clear of a win.
> > So this patch instead makes us only consider this optimization for
> > sized ranges.
> >
> >       PR libstdc++/121917
> >
> > libstdc++-v3/ChangeLog:
> >
> >       * include/bits/ranges_algo.h (__shuffle_fn::operator()): Only
> >       consider the two-at-a-time PRNG optimization if the range is
> >       sized.
> >       * testsuite/25_algorithms/shuffle/constrained.cc (test03): New
> >       test.
>
> Whoops, forgot to --amend the commit.  This is the correct diff:

Nice, thanks. OK for trunk.


>
> -- >8 --
>
> Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
>
> ---
>  libstdc++-v3/include/bits/ranges_algo.h        | 11 ++++++++++-
>  .../25_algorithms/shuffle/constrained.cc       | 18 ++++++++++++++++++
>  2 files changed, 28 insertions(+), 1 deletion(-)
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> index 6e1e06cb2d0f..f886edbb952c 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -1964,9 +1964,10 @@ namespace ranges
>         using __uc_type
>           = common_type_t<typename remove_reference_t<_Gen>::result_type, __ud_type>;
>
> +       if constexpr (sized_sentinel_for<_Sent, _Iter>)
> +         {
>             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.
>               {
> @@ -1999,6 +2000,7 @@ namespace ranges
>
>                 return __i;
>               }
> +         }
>
>         __distr_type __d;
>
> @@ -2015,6 +2017,13 @@ namespace ranges
>        borrowed_iterator_t<_Range>
>        operator()(_Range&& __r, _Gen&& __g) const
>        {
> +       if constexpr (sized_range<_Range>
> +                     && !sized_sentinel_for<sentinel_t<_Range>,
> +                                            iterator_t<_Range>>)
> +         return (*this)(ranges::begin(__r),
> +                        ranges::begin(__r) + ranges::size(__r),
> +                        std::forward<_Gen>(__g));
> +       else
>           return (*this)(ranges::begin(__r), ranges::end(__r),
>                          std::forward<_Gen>(__g));
>        }
> 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
>
  

On Fri, 12 Sept 2025 at 21:57, Patrick Palka <ppalka@redhat.com> wrote:
>
> On Fri, 12 Sep 2025, Patrick Palka wrote:
>
> > On Fri, 12 Sep 2025, Jonathan Wakely wrote:
> >
> > > On Fri, 12 Sept 2025 at 18:39, Patrick Palka <ppalka@redhat.com> 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
> > > > 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)
> > >
> > > This _S_impl should be private, however ...
> > >
> > > >        {
> > > >         // 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)
> > >
> > > Having this as a runtime check for != 1 seems a little inelegant when
> > > we've already determined statically whether we want to consider the
> > > optimization.
> > >
> > > We could leave the main implementation in the operator()(Iter, Sent,
> > > Gen&&) overload and just add:
> > >
> > > if constexpr (sized_sentinel_for<Sent, Iter>)
> > >
> > > here instead of 'if ( n != 1)'
> > >
> > > Then in the operator()(R&&, Gen&&) overload do:
> > >
> > >     if constexpr (sized_range<_Range>)
> > >       {
> > >         auto __first = ranges::begin(__r);
> > >         return (*this)(__first, __first + ranges::size(__r),
> > >                std::forward<_Gen>(__g));
> > >       }
> > >     else
> > >       return (*this)(ranges::begin(__r), ranges::end(__r),
> > >              std::forward<_Gen>(__g));
> > >
> > > This way we don't need to pass n to _S_impl, we just ensure that we
> > > pass a sized sentinel instead, and that enables the optimization.
> >
> > Sounds good, like so?
> >
> > -- >8 --
> >
> > Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
> >
> > 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
> > non-sized sentinel which makes the optimization less clear of a win.
> > So this patch instead makes us only consider this optimization for
> > sized ranges.
> >
> >       PR libstdc++/121917
> >
> > libstdc++-v3/ChangeLog:
> >
> >       * include/bits/ranges_algo.h (__shuffle_fn::operator()): Only
> >       consider the two-at-a-time PRNG optimization if the range is
> >       sized.
> >       * testsuite/25_algorithms/shuffle/constrained.cc (test03): New
> >       test.
>
> Whoops, forgot to --amend the commit.  This is the correct diff:
>
> -- >8 --
>
> Subject: [PATCH] libstdc++: Fix ranges::shuffle for non-sized range [PR121917]
>
> ---
>  libstdc++-v3/include/bits/ranges_algo.h        | 11 ++++++++++-
>  .../25_algorithms/shuffle/constrained.cc       | 18 ++++++++++++++++++
>  2 files changed, 28 insertions(+), 1 deletion(-)
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> index 6e1e06cb2d0f..f886edbb952c 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -1964,9 +1964,10 @@ namespace ranges
>         using __uc_type
>           = common_type_t<typename remove_reference_t<_Gen>::result_type, __ud_type>;
>
> +       if constexpr (sized_sentinel_for<_Sent, _Iter>)
> +         {
>             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.
>               {
> @@ -1999,6 +2000,7 @@ namespace ranges
>
>                 return __i;
>               }
> +         }
>
>         __distr_type __d;
>
> @@ -2015,6 +2017,13 @@ namespace ranges
>        borrowed_iterator_t<_Range>
>        operator()(_Range&& __r, _Gen&& __g) const
>        {
> +       if constexpr (sized_range<_Range>
> +                     && !sized_sentinel_for<sentinel_t<_Range>,
> +                                            iterator_t<_Range>>)
> +         return (*this)(ranges::begin(__r),
> +                        ranges::begin(__r) + ranges::size(__r),

Oops, the addition needs to use
range_difference_t<Range>(ranges::size(__r)), or just
ranges::distance(__r). We know ranges::distance will be O(1) because
it's a sized_range.


> +                        std::forward<_Gen>(__g));
> +       else
>           return (*this)(ranges::begin(__r), ranges::end(__r),
>                          std::forward<_Gen>(__g));
>        }
> 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
>
  

On Fri, Sep 12, 2025 at 7:39 PM Patrick Palka <ppalka@redhat.com> 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
>
>
  

On Mon, 22 Sep 2025, Tomasz Kaminski wrote:

> 
> 
> On Fri, Sep 12, 2025 at 7:39 PM Patrick Palka <ppalka@redhat.com> 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? 

Oops, yes.

>       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
> 
> 
>