HOWTO · C++

Mélange de vecteurs en C++

Cet article présente la manière de mélanger un vecteur en C++

Sur cette page

Pour réordonner aléatoirement les éléments d’un vecteur C++ sur place, appelez std::shuffle avec les itérateurs begin() et end() du vecteur ainsi qu’un moteur de nombres aléatoires. L’algorithme réorganise les éléments de la plage fournie ; il ne crée pas un second vecteur. Utilisez une graine fixe pour le moteur si vous souhaitez obtenir une séquence de choix pseudo-aléatoires reproductible, ou initialisez-le à partir d’une source appropriée si vous voulez que les différentes exécutions produisent généralement des séquences différentes.

Mélanger un vecteur avec std::shuffle

std::shuffle est déclaré dans l’en-tête <algorithm>. Ses deux premiers arguments délimitent une plage d’itérateurs semi-ouverte : le premier itérateur désigne le premier élément à inclure et le second pointe juste après le dernier. Pour un vecteur, values.begin() et values.end() couvrent donc l’ensemble de ses éléments. Le troisième argument est un générateur uniforme de bits aléatoires (UniformRandomBitGenerator), souvent un moteur tel que std::mt19937. Le moteur fournit les bits aléatoires utilisés pour choisir la permutation ; ce n’est pas une fonction de rappel qui renvoie un vecteur déjà mélangé.

Cet exemple complet utilise une graine fixe afin que le moteur parte du même état à chaque exécution du programme. std::shuffle ne garantit pas un ordre mélangé particulier : celui-ci peut varier selon l’implémentation de la bibliothèque standard. Considérez donc la sortie ci-dessous comme un exemple et non comme une séquence garantie.

Exécutez cet exemple :

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <vector>

int main() {
    std::vector<int> values{12, 32, 43, 53, 23, 65, 84};
    std::mt19937 engine(42);

    std::shuffle(values.begin(), values.end(), engine);

    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) {
            std::cout << ' ';
        }
        std::cout << values[i];
    }
    std::cout << '\n';
}

Le vecteur d’entrée contient 12 32 43 53 23 65 84. Lors de l’exécution réussie fournie, le programme a affiché cet ordre mélangé :

23 12 43 53 84 65 32

Avec une graine fixe, la séquence du moteur pseudo-aléatoire est reproductible avec la même implémentation et la même configuration. Cela ne garantit pas un résultat mélangé identique avec toutes les implémentations de bibliothèque standard, car l’algorithme ne définit pas une séquence universelle de choix. Pour obtenir des résultats qui varient d’une exécution à l’autre, initialisez un moteur une seule fois, puis réutilisez-le pour les mélanges, au lieu d’en créer un nouveau pour chaque élément ou chaque appel. std::random_device sert souvent de source de graine, mais son comportement dépend de l’implémentation et de l’environnement ; il ne faut pas le présenter comme une garantie de non-déterminisme ou de caractère cryptographique.

Vous pouvez aussi exprimer la plage avec std::begin(values) et std::end(values), disponibles avec les utilitaires standard pour itérateurs. Cette forme est utile pour écrire une fonction générique qui accepte différents types de conteneurs ou des tableaux intégrés. Pour un appel propre à un vecteur, ses itérateurs membres sont directs et clairs. Dans les deux cas, passez les deux extrémités du même conteneur et vérifiez que la plage contient bien les éléments à permuter. L’opération modifie l’ordre du vecteur sur place : le code qui le lit ou le parcourt ensuite voit donc l’ordre mélangé.

Gérer le code existant qui utilise std::random_shuffle

std::random_shuffle est un ancien algorithme de la bibliothèque standard que l’on peut trouver dans du code C++ existant. Sa disponibilité dépend de la norme de langage sélectionnée par le projet et de l’implémentation de la bibliothèque utilisée. Lors de la maintenance de ce code, vérifiez ces paramètres avant de supposer que ce nom est disponible. Les anciennes surcharges peuvent utiliser une source d’aléa définie par l’implémentation, tandis que celles qui acceptent un générateur ont des exigences différentes de celles imposées au moteur passé à std::shuffle.

Pour le code nouveau ou mis à jour, préférez std::shuffle et passez-lui un moteur de nombres aléatoires explicite. La source d’aléa est ainsi visible, vous pouvez contrôler la reproductibilité à l’aide d’une graine et vous évitez de dépendre de l’ancienne interface. Ne déduisez pas de la présence de std::random_shuffle dans un code source que cet algorithme est disponible dans tous les modes du compilateur, ni que std::shuffle est absent de tout environnement plus ancien : la compatibilité dépend de la configuration du projet, de sa bibliothèque standard et de sa norme de langage. Si un projet doit conserver du code ancien, limitez ce choix de compatibilité à ce projet et vérifiez-le avec la configuration du compilateur utilisée pour le construire.