Comment mélanger un std::vector ?

Question

Je cherche un moyen générique et réutilisable de mélanger une std::vector en C++. C'est ainsi que je le fais actuellement, mais je pense que ce n'est pas très efficace car il faut un tableau intermédiaire et il faut connaître le type d'élément (DeckCard dans cet exemple) :

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

À partir de C++11, il faut préférer :

#include <algorithm>
#include <random>

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

<a href="http://coliru.stacked-crooked.com/a/5532a28aa687a0a8" rel="noreferrer">Live example on Coliru</a>

Veillez à réutiliser la même instance de rng à travers de multiples appels à std::shuffle si vous avez l'intention de générer des permutations différentes à chaque fois !

De plus, si vous souhaitez que votre programme crée des séquences de mélange différentes à chaque exécution, vous pouvez utiliser le constructeur du moteur aléatoire avec la sortie de la commande std::random_device :

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

---

Pour C++98, vous pouvez utiliser :

#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

En plus de ce que @Cicada a dit, vous devriez probablement semer en premier,

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

Par le commentaire de @FredLarson :

la source du caractère aléatoire pour cette version de random_shuffle() est est définie par l'implémentation, donc elle peut ne pas utiliser rand() du tout. Dans ce cas, srand() n'aurait aucun effet.

Donc YMMV.

Answer 4

Il peut être encore plus simple, l'ensemencement peut être entièrement évité :

#include <algorithm>
#include <random>

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

Cela produira un nouveau shuffle à chaque fois que le programme sera exécuté. J'aime aussi cette approche en raison de la simplicité du code.

Cela fonctionne parce que tout ce dont nous avons besoin pour std::shuffle est un UniformRandomBitGenerator dont les exigences std::random_device rencontre.

Remarque : en cas de brassage répété, il peut être préférable d'enregistrer le fichier random_device dans une variable locale :

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

Answer 5

Si vous utilisez booster vous pouvez utiliser cette classe ( debug_mode est réglé sur false si vous voulez que la randomisation soit prévisible entre les exécutions, vous devez le définir à 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_));
    }
};

Ensuite, vous pouvez le tester avec ce 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;
}