What are best practices for simple random shuffling in code that's both C++03 and C++14?

Question

Background: I'm shuffling the elements of a vector for a simple game. It should be possible to play the same game over again by passing the same integer seed — and vice versa, different seeds should produce different games. Cryptographic security (or any rigor at all) is not a design goal; cleanliness of code is a design goal.

C++98/C++03 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, random_shuffle has been deprecated (source: N3924). The C++14 way of shuffling a deck is

int seed = ...;

std::vector<int> deck = ...;
std::shuffle(deck.begin(), deck.end(), std::mt19937(seed));

Here are the things that detract from each approach:

• The srand/random_shuffle way is deprecated in C++14, so we shouldn't use it.

• On some implementations, random_shuffle appears not to take its seed from srand, i.e., seeding with a different value doesn't produce different output! (libstdc++ on Linux doesn't have this issue, but Xcode on OSX 10.9.5 does.)

• The shuffle/mt19937 way isn't part of C++03, so we can't use it.

• The shuffle/mt19937 way appears to require that we pass the seed all the way down into the deck-shuffling code. For my application, I'd prefer to just "set it and forget it" via a mechanism such as srand that hides the global variable, rather than have to define my own global PRNG of type mt19937. In other words: I don't want to be bothered with PRNG details, I just want to shuffle my vector!

• I am mildly worried about thread-safety (being able to simultaneously shuffle two different decks from different threads), but obviously not about thread-safety and "seedableness" at the same time. Consider thread-safety a "nice-to-have".

The first candidate I've thought of is:

• bite the bullet and pass int seed all the way down into the deck-shuffling code (avoiding global variables)

• use something like #if __cplusplus >= 20110000 to use random_shuffle pre-C++11 and shuffle post-C++11

• to work around the srand "bug" on OSX, use the three-argument version of random_shuffle with some complicated functor... this sounds ugly

The second candidate is:

• screw C++03; just drop support for any implementation that doesn't provide std::shuffle and std::mt19937 out of the box

But is there some nice way to solve this problem? I know it's a problem that nobody has unless their program is a toy program; but there must be hundreds of toy programs out there that have hit this problem!

Answer 1

First, develop a desired interface. It should hide from user any platform/compiler specifics, but give you all necessary data for implementation. Write an unit test with a desired usage. Something like this:

int seed = ...;
std::vector<int> deck = ...;
my_shuffle(deck.begin(), deck.end(), seed);

Then 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 detect reliably Mac OS X, iOS, Linux, Windows in C preprocessor?

Answer 2

boost::random::mt19937 as a fallback? I do this for threads with little worry.

Answer 3

Even in C++11, distributions are not standardized in implementation.

Write your own shuffler (for each element, swap it with another random elememt) and random number generator/distribution. Weak, slow random number generators are short and simple.

I would pass your 'random factory' on down, and habe a method to 'fork' on thread spawning, as doing so also lets you do multiple 'runs' in the same execution. Having explicit state instead of global is usually worthwhile. But not needed if single threaded: just stuff the random factory into some global state and hold your nose.

There is no random shuffle that will bridge C++03 to C++17, so embrace a short hand written one. It also ensures the same behaviour on multiple platforms, which is useful for a number of reasons (test coverage (same on different platforms), cross platform testing (bug on OS/X can be debugged on Windows), portability of myriads of stuff (save game files, io-based network gameplay, etc)).

Answer 4

I might be tempted to do something like this. It solves the "passing down the seed" problem by wrapping it up in a custom class. In order to make that less work I have privately inherited from std::vector<int> and just implemented those functions I actually need for a deck.

Private inheritance gives me some protection by making sure I can not assign a deck* to its base pointer (and thus avoid non-virtual destructor problems).

#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';
}