std::random_shuffle is deprecated in C++14

published at 05.02.2015 21:18 by Jens Weller
Save to Instapaper Pocket

So, one of the new things in C++14 is, that the committee has actually started to deprecate (and later remove) a few things from the standard. One of them is a rather awkward function: random_shuffle.

In all the years, I think I used it only a few times. One use was to shuffle the "cards" in a black jack game I wrote for fun. The other was shuffling the play list of my mp3 player. And in some use cases, its even more important that you can't guess the order of certain elements.

Now, with the Call for Papers for Meeting C++ 2015 starting soon, I will need exactly that functionality. As I want a new feature in the online voting tool: random order for talks. This is very important, otherwise the talks first submitted might get a little bit better votes as the last submitted talks. As not every body is clicking and voting through all talks, and more important: if there are 2 talks on the same or a similar topic, people tend to vote a little better for the first. The voting is anonymous, so that you also cannot see the speakers name. And as mentioned, if the order isn't random, the vote distribution isn't equal.

The online voting tool is written php, but certain parts are generated from my C++ backend, that includes the talk and voting data.

A good case for random_shuffle:

std::vector<int> talk_ids;//all talk ids
std::random_shuffle(talk_ids.begin(),talk_ids.end());

Now, the order of the talks is random. The tool will load from a data source the data by talk id, and save the vote. But of course, the order needs to be different for every voter, otherwise the same problems occur as mentioned above. So when generating the php code, I should shuffle the talk_ids vector for each voting set. But, as already mentioned, random_shuffle is deprecated in C++14. What does that mean?

What deprecated actually means for random_shuffle

History knows 3 different versions of random shuffle:

// 1
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );

//2
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );

// 3
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );

In C++11, the version number 2 was changed in version 3. C++14 deprecates those versions now in favor of the shuffle algorithm. This means, random_shuffle will be removed from C++ with C++17. So, when you use it in C++11, you already should change it to shuffle, in C++14 you will get a warning for using a deprecated function. The attribute deprecated is a C++14 feature.

The reason for removing random_shuffle is, that the iterator only version is usually depending on std::rand, which is now also discussed for deprecation, and should be replaced with the classes of the <random> header, as std::rand is considered harmful. Also the iterator-only random_shuffle version usually depends on a global state. The shuffle algorithm is the replacement, and has as its 3rd parameter a URNG (Uniform Random Number Generator):

template< class RandomIt, class URNG >
void shuffle( RandomIt first, RandomIt last, URNG&& g );

The requirements for this URNG type are defined by the standard, and implemented in URNG classes of the <random> header, which has its origins in the boost random library. So, using shuffle is fairly easy, but requires the setup of the random number generator:

std::random_device rng;
std::mt19937 urng(rng());
std::shuffle(talk_ids.begin(), talk_ids.end(), urng);

Those 3 lines need a little bit of explanation:

• random_device is a uniform random number generator, which gives you 'pure randomness', but that might come with a light performance price. A pseudo random number generator can do much better.
• mt19937 is such a pseudo RNG, which needs to be initialized with a random value (aka 4).
• shuffle is then doing the same as random_shuffle with a random function.

So, random_device will give you a random number, and this number is used to initialize the URNG, which then is going to be used in shuffle. The standard offers several different RNG, the mersenne twister based RNG is a good default, also its available in a 64 bit version.

So, shuffle needs a little more setup then random_shuffle, but that gives you also more options.

Join the Meeting C++ patreon community!
This and other posts on Meeting C++ are enabled by my supporters on patreon!