melange d'elements dans vector crée doublons

Version imprimable

Bonjour,

je stocke une jeu de cartes dans un vector, et j'ai écrit une méthode permettant de mélanger les cartes.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Croupier
    {
        public :
 
            static std::vector<Carte> Paquet;
            static std::vector<Carte> Defausse;
 
            Croupier() {/*nothing to do */}
 
            ~Croupier() {/*nothing to do*/}
 
            void Melanger()
            {
                int i = 0;
                for (auto c : Paquet)
                {
                    do
                    {
                        i = rand() % Paquet.size();
                    }while (Paquet.at(i) == c);
 
                    std::swap(c, Paquet.at(i));
                }
            }

dans le main :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
 
std::vector<Carte> Jeu::Croupier::Paquet;
 
int main()
{
    //initialisation des textures des cartes
    Carte::InitTextureCartes();
    //initialisation de la graine
    srand((unsigned)time(NULL));
 
    //instanciation de la fenetre
    sf::RenderWindow App(sf::VideoMode(width,height,32), "testSFML");
 
    //instanciation des joueurs
    Joueurs::Joueur j1("Kamui"), j2("Alu"), j3("7"), j4("TeK");
 
    //instanciation du croupier
    Jeu::Croupier c;
 
    //le croupier choisit un jeu de 32 cartes
    c.Init_32_cartes();
 
    c.Melanger();
 
    Joueurs::Distribuer(Jeu::Croupier::Paquet);
    //[...]

Apres c.init_32_cartes(); si je vérifie le contenu du vector rien à dire, tout est normal.

Apres c.Melanger();, des doublons sont apparus et (forcément) des cartes ont disparu...

Je cherche depuis un bon moment une explication maintenant, mais je ne trouve rien dans cet algo qui ne pose problème...

(j'ai un petit doute sur ce que fait swap dans mon cas d'utilisation...)

Vous avez une idée?

j'ai suivi mon instinct et :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void Melanger() { int i = 0; int j = 0; for (auto c : Paquet) { do { i = rand() % Paquet.size(); }while (i != j); std::swap(Paquet.at(j), Paquet.at(i)); j++; } }
là je n'ai plus de doublons...

Je ne comprends pas ce qui ne va pas avec le swap précédent...

[HS]
je viens de m'apercevoir aussi que les cartes affichées sont toujours les mêmes (erreur classique de gestion du rand), mais je pensais avoir fait exactement ce qu'il fallait (initialisaiton de la graine dans le main, pour que ce ne soit fait qu'une fois, et ensuite bah utilisation de rand...)
[/HS]

14/09/2012, 10h06
Arzar
Bonjour,
Avant toute chose, pour mélanger un paquet de carte, la manière la plus simple reste d'utiliser std::random_shuffle() ;)
Code:

1 2 3 4 void Melanger() { std::random_shuffle(Paquet.begin(), Paquet.end()); }
Mais sinon pour le problème initial, il vient de l'erreur classique de l'utilisation de la boucle range-based for (et qui je soupçonne entrera rapidement au hit parade des bugs les plus courant en C+11). Dans ce code :

Code:

for (Carte c : Paquet)

c est une carte temporaire, une copie d'une carte appartenant au Paquet donc std::swap(c, Paquet.at(i)); swap la carte numéro i avec une carte temporaire.
Il faut écrire :

Code:

for (Carte& c : Paquet)

si l'on veut une sémantique de référence.

Personnellement je haie cette manie d'utiliser auto dans une boucle range-based for, une des raisons étant qu'auto masque le type réel et encourage ce genre d'erreur.
14/09/2012, 10h13
Kaamui
Citation:
Envoyé par Arzar

Bonjour,
Avant toute chose, pour mélanger un paquet de carte, la manière la plus simple reste d'utiliser std::random_shuffle() ;)

Code:

1 2 3 4 void Melanger() { std::random_shuffle(Paquet.begin(), Paquet.end()); }

Mais sinon pour le problème initial, il vient de l'erreur classique de l'utilisation de la boucle range-based for (et qui je soupçonne entrera rapidement au hit parade des bugs les plus courant en C+11). Dans ce code :

Code:

for (Carte c : Paquet)

c est une carte temporaire, une copie d'une carte appartenant au Paquet donc std::swap(c, Paquet.at(i)); swap la carte numéro i avec une carte temporaire.
Il faut écrire :

Code:

for (Carte& c : Paquet)

si l'on veut une sémantique de référence.

Personnellement je haie cette manie d'utiliser auto dans une boucle range-based for, une des raisons étant qu'auto masque le type réel et encourage ce genre d'erreur.
merci pour ta réponse, je vais suivre tes conseils. Pour l'utilisation (intempestive) de auto, c'est que j'ai lu qu'il était mieux de l'utiliser autant que possible, car cela améliore les performances.

C'est vrai finalement ?

J'ai toujours l'erreur basique "toujours le meme résultat après relance du programme", il faut faire quoi avec std::random_shuffle ?

Edit : OK, il faut quand même le srand(time(NULL)); T'aurais pas un truc moins C-ien en stock ?
14/09/2012, 10h39
Arzar
Citation:

Envoyé par Kaamui

merci pour ta réponse, je vais suivre tes conseils. Pour l'utilisation (intempestive) de auto, c'est que j'ai lu qu'il était mieux de l'utiliser autant que possible

Oui, herb sutter par exemple conseille régulièrement de l'utilser dès que possible, perso ça me hérisse le poil et je ne vois pas ce qu'on gagne réellement à écrire for(auto& c : Paquet) au lieu de for(Carte& c : Paquet) (sauf que c'est plus clair qu'on manipule des Carte dans le deuxième cas)

Citation:

Envoyé par Kaamui

, car cela améliore les performances

Non, ça c'est faux les performances sont exactement identique dans ce cas.
Je pense que tu confonds avec qqchose du style :
Code:

1 2 3 auto lambda = [] (){do_something();}; std::function<void()> f = [] (){do_something();};
Dans ce cas, en effet auto est plus performant vu qu'il permet de conserver le vrai type de la lambda, au lieu de devoir copier la lambda dans une std::fonction (donc avec potentiellement un new et un appel à une fonction virtuelle)

Citation:

Envoyé par Kaamui

Edit : OK, il faut quand même le srand(time(NULL)); T'aurais pas un truc moins C-ien en stock ?

Si tu es en C++11, il y a le nouveau header <random> qui permet de faire :
Code:

1 2 3 4 5 6 7 void Melanger() { std::random_device rd; std::default_random_engine re(rd()); std::shuffle(Paquet.begin(), Paquet.end(), re); }
Les résultats sont différents à chaque fois, sans avoir besoin de faire un srand(time(NULL)) au début du programme. Après ça vaut peut être le coup de n'instancier le random_device et le default_random_engine qu'une seule fois plutôt qu'à chaque appel de Mélanger(), je ne sais pas.
14/09/2012, 10h42
Kaamui
Citation:
Envoyé par Arzar

Oui, herb sutter par exemple conseille régulièrement de l'utilser dès que possible, perso ça me hérisse le poil et je ne vois pas ce qu'on gagne réellement à écrire for(auto& c : Paquet) au lieu de for(Carte& c : Paquet) (sauf que c'est plus clair qu'on manipule des Carte dans le deuxième cas)

Non, ça c'est faux les performances sont exactement identique dans ce cas.
Je pense que tu confonds avec qqchose du style :

Code:

1 2 3 auto lambda = [] (){do_something();}; std::function<void()> f = [] (){do_something();};

Dans ce cas, en effet auto est plus performant vu qu'il permet de conserver le vrai type de la lambda, au lieu de devoir copier la lambda dans une std::fonction (donc avec potentiellement un new et un appel à une fonction virtuelle)

Si tu es en C++11, il y a le nouveau header <random> qui permet de faire :

Code:

1 2 3 4 5 6 7 void Melanger() { std::random_device rd; std::default_random_engine re(rd()); std::shuffle(Paquet.begin(), Paquet.end(), re); }

Les résultats sont différents à chaque fois, sans avoir besoin de faire un srand(time(NULL)) au début du programme. Après ça vaut peut être le coup de n'instancier le random_device et le default_random_engine qu'une seule fois plutôt qu'à chaque appel de Mélanger(), je ne sais pas.
ok merci encore pour ton aide, je vais regarder tout ça ;)

Edit : j'ai une exception qui est levée avec le bout de code (que j'ai bêtement copié-collé)de Mélanger comme ça ; ça fonctionne pas juste comme ça ?

Citation:

terminate called after throwing an instance of 'std::runtime_error'
what(): random_device::random_device(const std::string&)

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Note qu'il est quand même possible de faire
Code:

1 2 3 for (auto& c : Paquet) {...} //ou même for (const auto& c : Paquet) {...}

14/09/2012, 10h55
Kaamui
Citation:
Envoyé par cob59

Note qu'il est quand même possible de faire

Code:

1 2 3 for (auto& c : Paquet) {...} //ou même for (const auto& c : Paquet) {...}
ouep ça je connaissais (je l'ai vu dans le topic sur gcc dans les explications sur le range-based for)

J'ai edit mon message car ce n'est pas totalement réglé malheureusement ^^
14/09/2012, 11h28
Arzar

Citation:

Envoyé par Kaamui

Edit : j'ai une exception qui est levée avec le bout de code (que j'ai bêtement copié-collé)de Mélanger comme ça ; ça fonctionne pas juste comme ça ?

Normalement oui, en tout cas sur Visual Studio 2012, ça fonctionne.
Mais ça demande un compilateur avec une biblio standard conforme au standard C++11.

En copiant collant le message d'erreur, je tombe sur ce sujet (http://www.gamedev.net/topic/622301-mingw-g-462-crash/) qui laisse entendre que ce bug vient de mingw.
J'ai l'impression que le plus sage reste d'utiliser ce bon vieux srand, au moins encore quelques années le temps que tous les compilos soient au point... :aie:
14/09/2012, 11h31
Kaamui

Citation:

Envoyé par Arzar

Normalement oui, en tout cas sur Visual Studio 2012, ça fonctionne.
Mais ça demande un compilateur avec une biblio standard conforme au standard C++11.

En copiant collant le message d'erreur, je tombe sur ce sujet (http://www.gamedev.net/topic/622301-mingw-g-462-crash/) qui laisse entendre que ce bug vient de mingw.
J'ai l'impression que le plus sage reste d'utiliser ce bon vieux srand, au moins encore quelques années le temps que tous les compilos soient au point... :aie:

Ok, merci pour l'info