How to shuffle a std::vector?

Question

I am looking for a generic, reusable way to shuffle a std::vector in C++. This is how I currently do it, but I think it's not very efficient because it needs an intermediate array and it needs to know the item type (DeckCard in this example):

srand(time(NULL));

cards_.clear();

while (temp.size() > 0) {
    int idx = rand() % temp.size();
    DeckCard* card = temp[idx];
    cards_.push_back(card);
    temp.erase(temp.begin() + idx);
}

Racket

nope. look up fisher-yates.... – Cultus

Try not to use rand(), there are better RNG APIs available (Boost.Random or 0x <random>). – Bethought

Linked: #147891 – Brooks

Answer 1

From C++11 onwards, you should prefer:

#include <algorithm>
#include <random>

auto rng = std::default_random_engine {};
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Live example on Coliru

Make sure to reuse the same instance of rng throughout multiple calls to std::shuffle if you intend to generate different permutations every time!

Moreover, if you want your program to create different sequences of shuffles each time it is run, you can seed the constructor of the random engine with the output of std::random_device:

auto rd = std::random_device {}; 
auto rng = std::default_random_engine { rd() };
std::shuffle(std::begin(cards_), std::end(cards_), rng);

---

For C++98 you may use:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());

Anisometric

You can also plug a custom random number generator as a third argument of std::random_shuffle. – Rosales

+1 - Note that this may produce an identical result every run of the program. You can add a custom random number generator (which can be seeded from an external source) as an additional argument to std::random_shuffle if this is a problem. – Koweit

It seems without srand(unsigned(time(NULL))), it always generate same result each time... – Lycaonia

@Gob00st: it will generate the same result for every instance of the program, not every call to random_shuffle. This behavior is normal and intended. – Anisometric

@cicada: Some random_shuffle() implementations call rand() internally(at least in the case of VS2008 and gcc), so without srand(), each instance can only generate same result which I am not sure if as useful as the case with srand() – Lycaonia

When coded as shown here, I found that std::shuffle() generates the same results on multiple sequential calls (within the same instance of the program) -- because the random engine is constructed in line. To resolve this you need to share a common instance of the default_random_engine or else construct it with a unique seed on each pass. – Microgroove

Dare I ask: why deprecate random_shuffle instead of just having it do your suggested alternative? – Tomtom

@Matt Because my answer was initially for C++98 where shuffle is not available. But indeed, I have updated my answer to suggest using the preferred function even in C++11, thank you! – Anisometric

Error: namespace "std" has no member "random_shuffle" – Screwdriver

@TomášZato #include <algorithm> – Anisometric

@ParkYoung-Bae Thanks, I just found out. It's really inconvenient when SO answers do not contain include info because their are on the top of google search results. – Screwdriver

@TomášZato I've updated my answer even though it's not really difficult to figure out (it's in one of the answers below...). – Anisometric

@ParkYoung-Bae it was unclear which import exactly is needed. (I somehow missed the explanatory comments) I guess you'd agree that figuring out includes (or anything else) isn't why people come here. – Screwdriver

Check this out, how to seed the generator, use random_device. So the code shall be std::random_device rd; std::default_random_engine engine{rd()}; – Distal

I think you should add how to seed this to your answer. A lot of people (that's me) come here because they googled "c++, shuffle vector". – Concertgoer

@Concertgoer My answer addresses specifically "how to shuffle a std::vector" no less, no more. Of course, I could add seeding, picking a random device, a generator, shuffling a sub-range, and so on, but that would be needlessly inflating this answer. I believe that seeding a RNG is a different question with a different, specific answer. But if you scroll down a bit, someone posted an answer with just that. – Anisometric

Why is the latter function superior? – Giffer

@stackptr In the C++98 function, you do not specify the generator, so std::rand is often use, but it is implementation defined. There are multiple reason why std::rand is considered bad nowadays, just google Why is std::rand bad?. Furthermore, the C++98 version is officially deprecated in C++14 and removed in C++17, so better switch to the C++11 version. – Courageous

Append to the answer: in my machine, I had to change from auto rd = std::random_device {}; to std::random_device rd;. In the former, I was getting the following error: error: calling a private constructor of class 'std::__1::random_device' – Englebert

I have a very similar use case: shuffling a deck of cards (std::vector<card>). I have copy and pasted the above solution exactly and tried other solutions I have found but always get the compiler error C2664 'void std::swap(std::exception_ptr &,std::exception_ptr &) noexcept': cannot convert argument 1 from 'card' to 'std::exception_ptr &'. Any ideas what might cause this in VS2017? I am stumped – Fachanan

Answer 2

http://www.cplusplus.com/reference/algorithm/shuffle/

// shuffle algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::shuffle
#include <vector>       // std::vector
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clock

int main () 
{
    // obtain a time-based seed:
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine e(seed);

    while(true)
    {
      std::vector<int> foo{1,2,3,4,5};

      std::shuffle(foo.begin(), foo.end(), e);

      std::cout << "shuffled elements:";
      for (int& x: foo) std::cout << ' ' << x;
      std::cout << '\n';
    }

    return 0;
}

Sulfide

a bad example copied from cplusplus.com/reference/algorithm/shuffle . How do you make another call of shuffle? – Latimer

@Latimer example improved – Sulfide

Why the weird use of the system clock for a seed instead of just using std::random_device? – Jounce

Answer 3

In addition to what @Cicada said, you should probably seed first,

srand(unsigned(time(NULL)));
std::random_shuffle(cards_.begin(), cards_.end());

Per @FredLarson's comment:

the source of randomness for this version of random_shuffle() is implementation defined, so it may not use rand() at all. Then srand() would have no effect.

So YMMV.

Sulfanilamide

Actually, the source of randomness for this version of random_shuffle() is implementation defined, so it may not use rand() at all. Then srand() would have no effect. I've run into that before. – Reata

@Fred: Thanks Fred. Did not know that. I have been used to using srand all the time. – Sulfanilamide

You should probably delete this answer as it is wrong and - even worse - it appears correct and indeed is correct in some implementations, but not all, making this advice very dangerous. – Red

As @Fred explained above what random_shuffle uses to generate random number is implementation defined. This means that on your implementation it uses rand() (and hence srand() works) but on mine it can use something totally different, meaning that on my implementation even with srand every time I run the program I will get the same results. – Red

@Andreas: That is beside the point. There is nothing wrong with using srand. – Sulfanilamide

@Andreas: It does work. You can also specify your own random number generator function to random_shuffle. – Sulfanilamide

@Code: like we discussed it doesn't work in all implementations. The fact that you can supply your own number generation is not mentioned in your answer and unrelated to this discussion in any case. I feel like we're going in circles :S – Red

@Andreas: I caveated the answer with Fred's comment. – Sulfanilamide

Answer 4

It can be even simpler, seeding can be avoided entirely:

#include <algorithm>
#include <random>

// Given some container `container`...
std::shuffle(container.begin(), container.end(), std::random_device());

This will produce a new shuffle each time the program is run. I also like this approach due to the simplicity of the code.

This works because all we need for std::shuffle is a UniformRandomBitGenerator, whose requirements std::random_device meets.

Note: if shuffling repeatedly, it may be better to store the random_device in a local variable:

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);

Yippie

What does this add that wasn't already part of the accepted answer from 8 years ago? – Camphor

All you have to do is read the answer to find out... There's not much more to be said that hasn't already been very clearly explained above. – Yippie

The accepted answer already uses shuffle, and says to use random_device ... – Camphor

The old accepted answer might be more in-depth. However, this is precisely the single-line point-and-shot answer I would expect when googling for such a simple question without much ado. +1 – Cabral

This is wrong. random_device is designed to be called only once to seed PRNGs, not to be called over and over again (which may exhaust the underlying entropy quickly and cause it switch to a sub-optimal generation scheme) – Arlynearlynne

That may be an important caveat to add, but it's very far from making this "wrong" as you so dramatically accuse. – Yippie

Answer 5

If you are using boost you could use this class (debug_mode is set to false, if you want that the randomizing could be predictable beetween execution you have to set it to true):

#include <iostream>
#include <ctime>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <boost/random/variate_generator.hpp>
#include <algorithm> // std::random_shuffle

using namespace std;
using namespace boost;

class Randomizer {
private:
    static const bool debug_mode = false;
    random::mt19937 rng_;

    // The private constructor so that the user can not directly instantiate
    Randomizer() {
        if(debug_mode==true){
            this->rng_ = random::mt19937();
        }else{
            this->rng_ = random::mt19937(current_time_nanoseconds());
        }
    };

    int current_time_nanoseconds(){
        struct timespec tm;
        clock_gettime(CLOCK_REALTIME, &tm);
        return tm.tv_nsec;
    }

    // C++ 03
    // ========
    // Dont forget to declare these two. You want to make sure they
    // are unacceptable otherwise you may accidentally get copies of
    // your singleton appearing.
    Randomizer(Randomizer const&);     // Don't Implement
    void operator=(Randomizer const&); // Don't implement

public:
    static Randomizer& get_instance(){
        // The only instance of the class is created at the first call get_instance ()
        // and will be destroyed only when the program exits
        static Randomizer instance;
        return instance;
    }

    template<typename RandomAccessIterator>
    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last){
        boost::variate_generator<boost::mt19937&, boost::uniform_int<> > random_number_shuffler(rng_, boost::uniform_int<>());
        std::random_shuffle(first, last, random_number_shuffler);
    }

    int rand(unsigned int floor, unsigned int ceil){
        random::uniform_int_distribution<> rand_ = random::uniform_int_distribution<> (floor,ceil);
        return (rand_(rng_));
    }
};

Than you can test it with this code:

#include "Randomizer.h"
#include <iostream>
using namespace std;

int main (int argc, char* argv[]) {
    vector<int> v;
    v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
    v.push_back(6);v.push_back(7);v.push_back(8);v.push_back(9);v.push_back(10);

    Randomizer::get_instance().random_shuffle(v.begin(), v.end());
    for(unsigned int i=0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    return 0;
}

Yvetteyvon

Why are you using time to seed the generator instead of std::random_device? – Jounce

Is boost random shuffle better than the normal shuffle? – Excellence

Answer 6

Depending of the standard you have to follow (C++11/C++14/C++17) this "cppreference" page provides pretty good examples: https://en.cppreference.com/w/cpp/algorithm/random_shuffle.

Surprisal