`<algorithm>`: Should `_Rng_from_urng` use `make-unsigned-like-t`?

[hewillk]

#include <vector>
#include <random>
#include <ranges>
#include <algorithm>

int main() {
  std::vector<std::size_t> v(10);
  std::ranges::sample(
    std::views::iota(0ULL, 42ULL),
    v.begin(), 3, std::mt19937{std::random_device{}()});
}

https://godbolt.org/z/bMredxf58

In the above example, the difference_type of iota_view is _Signed128, which makes the instantiation of _Rng_from_urng fail since it uses make_unsigned_t which cannot work with integer-class types.

STL/stl/inc/xutility

Lines 5696 to 5700 in ef62d3f

	template <class _Diff, class _Urng>
	class _Rng_from_urng { // wrap a URNG as an RNG
	public:
	using _Ty0 = make_unsigned_t<_Diff>;
	using _Ty1 = typename _Urng::result_type;

It's worth noting that gcc will only work with -std=gnu++20 because __int128 is an integer type only in gnu-mode. gcc will also fail the static_assert under -std=c++20, but this assertion comes from the implementation of std::sample, so there is no reference value because std::sample is not for C++20 iterators system.

In [alg.random.sample], I don't see any requirement that the above code violates, so should I consider it a bug?

[CaseyCarter]

Yes, this is a bug. It looks like size_t _Bmask is going to be limiting, but we can't change the layout of _Rng_from_urng - we'll probably need a partial specialization _Rng_from_urng<_Signed128, _Urng>.

[hewillk]

Note that ranges::shuffle has the same problem since it also uses _Rng_from_urng.

#include <algorithm>
#include <ranges>
#include <vector>
#include <random>

int main() {
  std::vector<int> v;
  auto r = std::views::iota(0ULL, v.size())
         | std::views::transform([&v](auto i) -> auto& { return v[i]; });
  std::ranges::shuffle(r, std::mt19937{std::random_device{}()});
}

https://godbolt.org/z/89Wa15GhT

[MattStephanson]

The algorithms only need to generate numbers in the range [0,size(r)). As long as that can be represented by an integral type, then generating number in the larger, signed difference_type is unnecessary.

It looks like size_t _Bmask is going to be limiting, but we can't change the layout of _Rng_from_urng

I think _Bmask is fine. It's a mask for the bits that can be generated in one call to the URBG. The allowed result types for a URBG are a subset of the integral types, so 64 bits should always be sufficient.

[StephanTLavavej]

Because _Rng_from_urng is an internal type that isn't persistently stored anywhere (it appears only as local variables), we can totally modify its definition and even its data member layout as long as we rename it to _Rng_from_urng_2. That will avoid any mix-and-match problems. We've done this in the past with internal parallel algorithms machinery.

This may be entirely moot - as Matt Stephanson (@MattStephanson) noted and Casey Carter (@CaseyCarter) agreed (in our weekly maintainer meeting), as _Bmask isn't limiting, there should be no need to change the layout and thus we can continue using the same name.

[frederick-vs-ja]

_Rng_from_urng_v2 has been moved to <random> (#3157). Should we move it to <algorithm> in order to fix this issue?