How to shuffle std :: vector?

Question

I am looking for a universal reusable way to shuffle std::vector in C ++. This is how I do it now, but I think it is not very efficient, because it needs an intermediate array, and it needs to know the element 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); } 

Answer 1

Starting with C ++ 11, 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

Be sure to use the same rng instance rng several calls to std::shuffle if you want to generate different permutations each time!

Moreover, if you want your program to create different shuffle sequences each time you start it, you can std::random_device constructor for a random engine with the output std::random_device .

---

For C ++ 98 you can use:

 #include <algorithm> std::random_shuffle(cards_.begin(), cards_.end()); 

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

Answer 3

In addition to what @Cicada said, you should probably go gray first.

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

For the comment by @FredLarson:

the source of randomness for this version of random_shuffle () is equal to the implementation is defined, so it cannot use rand () at all. Then srand () will have no effect.

So, YMMV.

Answer 4

If you use boost , you can use this class ( debug_mode set to false , if you want randomization to be predictable between execution, you should 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_)); } }; 

How can you 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; }