Is random_shuffle threadsafe? and using rand_r if

Question

Is std::random_shuffle threadsafe? I presume not since the regular rand() is not threadsafe. If that is the case, how would I use rand_r with random_shuffle so that I can give each thread a unique seed. I've seen examples of using custom random generators with random_shuffle, but it is still unclear to me.

Thanks.

Answer 1

You need to provide a random number generator function or functor object that takes an integral value type and returns another value of some integral type that will not overflow the bounds of the container that the iterators you've passed into the function are iterating through. Also in the case of a functor object, it must implement the operator() so that it can be called like a function. Because you need a thread-safe random-number generator, using srand and rand from cstdlib is a bad idea ... you should instead create some functor object that implements a thread-safe random-number generator, or a random-number generator that does not implement globally accessible variables so that everything remains thread-local storage.

So for instance, one way this could work is you have some type of random number generator you've gotten from another library that will only generate random values between a fixed range of values so you can define the bounds of the container for the random-access iterators the random_shuffle algorithm uses. Now depending on what library you use, you functor could look something like the following:

class my_rand_gen
{
   private:
       random_gen_type random_range_gen;
       int min;
       int max;

   public:
       my_rand_gen(const random_gen_type& gen, int min_range, int max_range):
                     random_range_gen(gen), min(min_range), max(max_range) {}

       int operator()(int value) 
       { 
           //ignore the input value and use our own defined range
           //returns a value between min and max
           return random_range_gen(min, max); 
       }
};

Now you can call the algorithm like:

random_shuffle(my_vector_start_iter, my_vector_end_iter, 
               my_rand_gen(rand_generator_lib, 
                           vector_start_index, 
                           vector_end_index));

and it will shuffle the vector in-between the start and end iterators to your vector without overflowing the bounds of the vector ... in other words it will only use values for the shuffle between vector_start_index and vector_end_index.

Answer 2

To use rand_r with std::random_shuffle, you'll need to write a (fairly trivial) wrapper. The random number generator you pass to random_shuffle needs to accept a parameter that specifies the range of numbers to be produced, which rand_r does not.

Your wrapper would look something like this:

class rand_x { 
    unsigned int seed;
public:
    rand_x(int init) : seed(init) {}

    int operator()(int limit) {
        int divisor = RAND_MAX/(limit+1);
        int retval;

        do { 
            retval = rand_r(&seed) / divisor;
        } while (retval > limit);

        return retval;
    }        
};

You'd use it with random_shuffle something like:

std::random_shuffle(whatever.begin(), whatever.end(), rand_x(some_seed));

Answer 3

Probably not.

Use the second version of adnrom_shuffle that takes a template parameter for the random number generator: http://www.sgi.com/tech/stl/random_shuffle.html. The generator must match: http://www.sgi.com/tech/stl/RandomNumberGenerator.html

struct MyRandomNumberGenerator
{
    int operator()(int limit) const
    {
         // get threadsafe random number
    }
};

// Stuff
random_shuffle(list.begin(), list.end(), MyRandomNumberGenerator());