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