What are the best practices for simple random shuffling of code, both C ++ 03 and C ++ 14?
Background: I drag and drop vector elements for a simple game. It should be possible to play the same game over and over again by passing the same whole seed - and vice versa, different seeds should produce different games. Cryptographic security (or any rigor) is not a design goal; code cleanliness is a design goal.
C ++ 98 / C ++ 03 is introduced std::random_shuffle
, which is used like this:
int seed = ...;
std::srand(seed); // caveat, see below
std::vector<int> deck = ...;
std::random_shuffle(deck.begin(), deck.end());
However, as of C ++ 14, it is random_shuffle
deprecated (source: N3924 ). The C ++ 14 way to shuffle the deck
int seed = ...;
std::vector<int> deck = ...;
std::shuffle(deck.begin(), deck.end(), std::mt19937(seed));
Here's what distracts each approach:
-
Method
srand
/ israndom_shuffle
deprecated in C ++ 14, so we shouldn't use it. -
In some implementations
random_shuffle
, it doesn't seem to take its seed fromsrand
, i.e. seeding with a different value doesn't give you any other output! (libstdc ++ on Linux doesn't have this issue, but Xcode on OSX 10.9.5 does.) -
The
shuffle
/ method ismt19937
not part of C ++ 03, so we cannot use it. -
It seems like the
shuffle
/ pathmt19937
requires us to pass the seed all the way down to the deck's drag code. For my application, I'd rather just "set it and forget" with a mechanism such assrand
that hides the global variable rather than having to define my own global PRNG typemt19937
. In other words: I don't want to worry about the PRNG details, I just want to shuffle my vector! -
I'm a bit worried about thread safety (being able to shuffle two different decks from different threads at the same time), but obviously not only with regard to thread safety and seed at the same time. Think of thread safety as "nice".
The first candidate I was thinking about is:
-
bite the bullet and pass
int seed
all the way down to the deck's drag code (avoiding globals) -
use something like
#if __cplusplus >= 20110000
to userandom_shuffle
pre-c ++ 11 andshuffle
post-c ++ 11 -
to work around the
srand
"bug" in OSX, use the 3-argument versionrandom_shuffle
with some tricky functor ... that sounds ugly
Second candidate:
- screw C ++ 03; just de-support any implementation that doesn't provide
std::shuffle
itstd::mt19937
out of the box
But is there a good way to solve this problem? I know this is a problem that no one else has unless their program is a toy program; but there must be hundreds of toy programs out there that hit this problem!
source to share
Even in C ++ 11, distributions are not standardized in implementation.
Write your own shuffler (for each item, swap it for another random item) and a random number generator / distribution. Weak, slow random number generators are short and simple.
I would pass your "random factory" down and fork as the thread grows, as this also allows multiple "runs" in the same execution. This is usually an explicit state, not a global one. But not needed if single threaded: just put a random factory in some kind of global state and keep your nose up.
There is no random shuffle that would traverse C ++ 03 to C ++ 17, so take a short handwritten note. It also provides the same behavior across multiple platforms, which is useful for a number of reasons (test coverage (same across platforms), cross-platform testing (bug in OS / X can be debugged on Windows), portability of myriad materials (save game files, network network based gameplay, etc.)).
source to share
First create your desired interface. It should hide some platform / compiler specifics from the user, but give you all the necessary data to implement. Write a unit test with your desired usage. Something like that:
int seed = ...;
std::vector<int> deck = ...;
my_shuffle(deck.begin(), deck.end(), seed);
Then we implement
template< typename IteratorType >
void my_shuffle( IteratorType first, IteratorType last,
int seed = some_default_seed_maybe )
{
#ifdef MACOS_FOUND
// Mac solution
#elif __cplusplus >= 201103L
// C++11 solution
#else
// fallback
}
Does it look clean enough?
Check also: How to reliably detect Mac OS X, iOS, Linux, Windows in C preprocessor?
source to share
I might be tempted to do something like this. It solves the miss-seed problem by wrapping it in a custom class. To make this work less, I have privately inherited from std::vector<int>
and just implemented the features I really need for deck
.
Private inheritance gives me some protection if I can't assign deck*
it to the base pointer (and thus avoid problems with a non-virtual destructor).
#if __cplusplus >= 201103L
class deck
: private std::vector<int>
{
int seed = 0;
public:
deck(int seed = 0): seed(seed) {}
// access relevant functions
using std::vector<int>::size;
using std::vector<int>::begin;
using std::vector<int>::end;
using std::vector<int>::push_back;
using std::vector<int>::operator=;
using std::vector<int>::operator[];
void shuffle()
{
std::shuffle(begin(), end(), std::mt19937(seed));
}
};
#else
class deck
: private std::vector<int>
{
typedef std::vector<int> vector;
typedef vector::iterator iterator;
int seed = 0;
public:
deck(int seed = 0): seed(seed) {}
// implement relevant functions
iterator begin() { return vector::begin(); }
iterator end() { return vector::end(); }
void push_back(int i) { vector::push_back(i); }
int& operator[](vector::size_type i) { return (*this)[i]; }
void shuffle()
{
std::srand(seed);
std::random_shuffle(begin(), end());
}
};
#endif
int main()
{
deck d(5);
d = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
d.shuffle();
for(unsigned i = 0; i < d.size(); ++i)
std::cout << d[i] << '\n';
}
source to share