https://gcc.gnu.org/g:349affa42c9fa47a12eb7f5f97f5650a77bbf014
commit r16-3842-g349affa42c9fa47a12eb7f5f97f5650a77bbf014 Author: Patrick Palka <[email protected]> Date: Sat Sep 13 10:44:12 2025 -0400 libstdc++: Fix ranges::shuffle for non-sized range [PR121917] ranges::shuffle has a two-at-a-time PRNG optimization (copied from std::shuffle) that considers the PRNG width vs the size of the range. But in C++20 a random access sentinel isn't always sized so we can't unconditionally do __last - __first to obtain the size in constant time. We could instead use ranges::distance, 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. Reviewed-by: Jonathan Wakely <[email protected]> Diff: --- libstdc++-v3/include/bits/ranges_algo.h | 66 +++++++++++++--------- .../testsuite/25_algorithms/shuffle/constrained.cc | 18 ++++++ 2 files changed, 56 insertions(+), 28 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 9b348d82ce55..6ec233f19df8 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -1968,40 +1968,43 @@ namespace ranges 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. + if constexpr (sized_sentinel_for<_Sent, _Iter>) { - _Iter __i = ranges::next(__first); - - // 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: + const __uc_type __urngrange = __g.max() - __g.min(); + const __uc_type __urange = __uc_type(__last - __first); - if ((__urange % 2) == 0) + if (__urngrange / __urange >= __urange) + // I.e. (__urngrange >= __urange * __urange) but without wrap issues. { - __distr_type __d{0, 1}; - ranges::iter_swap(__i++, ranges::next(__first, __d(__g))); - } + _Iter __i = ranges::next(__first); - // 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: + // 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: - while (__i != __last) - { - const __uc_type __swap_range = __uc_type(__i - __first) + 1; + if ((__urange % 2) == 0) + { + __distr_type __d{0, 1}; + ranges::iter_swap(__i++, ranges::next(__first, __d(__g))); + } - const pair<_DistanceType, _DistanceType> __pospos = - __gen_two_uniform_ints(__swap_range, __swap_range + 1, __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: - ranges::iter_swap(__i++, ranges::next(__first, __pospos.first)); - ranges::iter_swap(__i++, ranges::next(__first, __pospos.second)); - } + while (__i != __last) + { + const __uc_type __swap_range = __uc_type(__i - __first) + 1; - return __i; + const pair<_DistanceType, _DistanceType> __pospos = + __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g); + + ranges::iter_swap(__i++, ranges::next(__first, __pospos.first)); + ranges::iter_swap(__i++, ranges::next(__first, __pospos.second)); + } + + return __i; + } } __distr_type __d; @@ -2021,8 +2024,15 @@ namespace ranges borrowed_iterator_t<_Range> operator()(_Range&& __r, _Gen&& __g) const { - return (*this)(ranges::begin(__r), ranges::end(__r), - std::forward<_Gen>(__g)); + 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(); }
