Fix random_sample_n and random_shuffle when RAND_MAX is small

Jonathan Wakely
Mon Jan 14 20:38:00 GMT 2019

On 12/12/18 22:31 +0100, Giovanni Bajo wrote:
>we hit a bug today while cross-compiling a C++ program with mingw32:
>if random_shuffle or random_sample_n are called with a sequence of
>elements whose length is higher than RAND_MAX, the functions don't
>behave as expected because they ignore elements beyond RAND_MAX. This
>does not happen often on Linux where glibc defines RAND_MAX to 2**31,
>but mingw32 (all released versions) relies on the very old msvcrt.lib,
>where RAND_MAX is just 2**15.
>I found mentions of this problem in 2011
>and 2006 (
>I'm attaching a proof-of-concept patch that fixes the problem by
>introducing an embedded xorshift generator, seeded with std::rand (so
>that the functions still depend on srand — it looks like this is not
>strictly required by the standard, but it sounds like a good thing to
>do for backward compatibility with existing programs). I was wondering
>if this approach is OK or something else is preferred.

I'd prefer not to introduce that change unconditionally. The existing
code works fine when std::distance(first, last) < RAND_MAX, and as we
have random access iterators we can check that cheaply.

We'd prefer a bug report in Bugzilla with a testcase that demonstrates
the bug. A portable regression test for our testsuite might not be
practical if it needs more than RAND_MAX elements, but one that runs
for mingw and verifies the fix there would be needed.

See for guidelines for
submitting patches (and the rest of the page for other requirements,
like copyright assignment or disclaimers).

More information about the Libstdc++ mailing list