Jak przetasować std:: vector?
Szukam ogólnego, wielokrotnego użytku sposobu na przetasowanie std::vector
w C++. Tak to obecnie robię, ale myślę, że nie jest to zbyt wydajne, ponieważ potrzebuje pośredniej tablicy i musi znać typ elementu (DeckCard w tym przykładzie):
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);
}
6 answers
Począwszy od C++11, powinieneś wybrać:
#include <algorithm>
#include <random>
auto rng = std::default_random_engine {};
std::shuffle(std::begin(cards_), std::end(cards_), rng);
Upewnij się, że używasz ponownie tej samej instancji rng
podczas wielu wywołań do std::shuffle
jeśli zamierzasz za każdym razem generować różne permutacje!
Ponadto, jeśli chcesz, aby twój program tworzył różne sekwencje tasowania za każdym razem, gdy jest uruchamiany, możesz zalać konstruktor losowego silnika z wyjściem std::random_device
:
auto rd = std::random_device {};
auto rng = std::default_random_engine { rd() };
std::shuffle(std::begin(cards_), std::end(cards_), rng);
Do C++98 możesz użyć:
#include <algorithm>
std::random_shuffle(cards_.begin(), cards_.end());
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2020-05-01 11:19:38
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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-04-07 15:41:09
Oprócz tego, co powiedział @Cykada, powinieneś chyba najpierw seed,
srand(unsigned(time(NULL)));
std::random_shuffle(cards_.begin(), cards_.end());
Za komentarz @FredLarson:
Źródłem losowości dla tej wersji random_shuffle() jest implementacja zdefiniowana, więc może w ogóle nie używać rand (). Następnie srand() nie przyniosłoby to żadnego efektu.
Więc YMMV.
Jeśli używasz boost możesz użyć tej klasy (debug_mode
jest ustawiona na false
, Jeśli chcesz aby randomizacja była przewidywalna musisz ustawić ją na 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_));
}
};
Niż można go przetestować za pomocą tego kodu:
#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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-02-10 15:43:12
Może być jeszcze prostsze, można całkowicie uniknąć siewu:
#include <algorithm>
#include <random>
// Given some container `container`...
std::shuffle(container.begin(), container.end(), std::random_device());
Spowoduje to nowe przetasowanie za każdym razem, gdy program zostanie uruchomiony. Podoba mi się również takie podejście ze względu na prostotę kodu.
To działa, ponieważ wszystko, czego potrzebujemy do std::shuffle
jest UniformRandomBitGenerator
, których wymagania std::random_device
spotkania.
Uwaga: w przypadku wielokrotnego tasowania, może być lepiej przechowywać random_device
w zmiennej lokalnej:
std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2019-12-06 01:49:02
W zależności od standardu, który musisz przestrzegać (C++11 / C++14/C++17) ta strona "cppreference" zawiera całkiem dobre przykłady: https://en.cppreference.com/w/cpp/algorithm/random_shuffle .
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2020-04-17 18:52:04