Réorganisation aléatoire

L’algorithme random_shuffle est conçu pour redistribuer aléatoirement les éléments d’une séquence. Cet algorithme est fourni sous la forme de deux surcharges déclarées comme suit dans l’en-tête <algorithm> :

template <class RandomAccessIterator> 
void random_shuffle(RandomAccessIterator premier, RandomAccessIterator dernier); 

template <class RandomAccessIterator, class RandomNumberGenerator> 
void random_shuffle(RandomAccessIterator premier, RandomAccessIterator dernier, 
    RandomNumberGenerator g);

À savoir

RandomAccessIterator est un itérateur à accès aléatoire. L’itérateur à accès aléatoire implémente toutes les opérations de l’itérateur bidirectionnel, et il ajoute les méthodes permettant de se déplacer d’un élément vers un autre en temps constant (0 (1)). La distance entre l’élément original et l’élément destination n’est pas importante. L’itérateur à accès aléatoire est donc aussi rapide pour aller de l’élément 1 à l’élément 37 qu’il l’est pour aller de l’élément 1 à l’élément 2.

Les itérateurs à accès aléatoire étant capables de se déplacer de plus de un élément à la fois, les opérateurs d’addition + et += et de soustraction - et -= sont définis. Ces itérateurs définissent également l’opérateur index []. Si ri est un itérateur à accès aléatoire, ri[n] renvoie le n-ième élément de la séquence.

Si nous pouvons comparer l’égalité d’un itérateur à accès aléatoire, il nous est également possible de comparer sa valeur. Les opérateurs « inférieur à » <, « supérieur à » >, « inférieur ou égal à » <= et « supérieur ou égal à » >= sont donc définis. « Inférieur à » < est le seul opérateur de base. Tous les autres peuvent être dérivés à partir de ce dernier.

random_shuffle

Ces algorithmes prennent en argument les itérateurs de début et de fin de la séquence dont les éléments doivent être mélangés. La seconde version de cet algorithme peut prendre en dernier argument un objet fonction (quelquefois appelé foncteur) comme celui que nous avions utilisé dans le code 9.1 pour générer des valeurs. Cet objet sera utilisé pour calculer les positions des éléments pendant le mélange.

Code 9.8 : algorithme de réorganisation aléatoire

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
   int tab[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 
   //On mélange les éléments de tab : 
   random_shuffle(tab, tab+10); 
   //On affiche le résultat : 
   int i; 
   for (i=0; i<10; i++) 
      cout << tab[i] << endl; 
}

Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)

Dernière modification le vendredi 30 octobre 2009 à 12:10:14.Ce document intitulé « Manipulation de données - Réorganisation aléatoire » issu de Comment Ça Marche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.