Manipulation de données - Initialisation et remplissage

Décembre 2016

Algorithmes

La bibliothèque standard définit tout un jeu de fonctions modèles extérieures aux conteneurs, dont le but est de réaliser toutes les sortes d’opérations de haut niveau sur leurs éléments. Ces fonctions sont appelées algorithmes en raison du fait qu’elles effectuent les traitements des algorithmes les plus connus et les plus utilisés en informatique.
Les algorithmes sont des fonctions modèles et peuvent donc, en pratique, être utilisés sur n’importe quelle structure de données ou n’importe quel conteneur, pourvu que certaines conditions initiales soient respectées.
La plupart des algorithmes de la bibliothèque standard sont déclarés dans l’en-tête <algorithm>, les autres sont disponibles avec le fichier en-tête <numeric>.

Le nombre des algorithmes définis par la bibliothèque standard est impressionnant et couvre la quasi-totalité des besoins d’un programmeur. Il est donc difficile, en raison de cette grande diversité, de les passer tous en revue. Les sections qui suivent présentent une sélection des algorithmes disponibles, regroupés en fonction de la nature des opérations qu’ils sont supposé effectuer. Ces opérations comprennent les opérations de manipulation générales des données, les recherches d’éléments selon des critères particuliers, les opérations de tri et de comparaison, et enfin les opérations de manipulation des conteneurs associatifs.

Manipulation des données

Il s’agit des opérations classiques de création, copie, suppression et remplacement, mais également de modification de l’ordre des séquences d’éléments ainsi que de traitement sur chacun des éléments des conteneurs.
Chaque algorithme sélectionné sera présenté par sa définition dans la bibliothèque standard suivie d’un exemple d’utilisation. La définition décrit la syntaxe exacte et l’ensemble des fonctions disponibles avec chaque algorithme.

Initialisation et remplissage

Il existe deux méthodes permettant d’initialiser un conteneur. La première se contente de générer plusieurs copies d’un même objet, que l’on spécifie par valeur, alors que la seconde permet d’appeler une fonction de génération pour chaque objet à créer.
Chaque algorithme est disponible sous deux formes différentes. La première utilise une paire d’itérateurs pointant sur le premier et le dernier élément à initialiser, et la seconde utilise un itérateur sur le premier élément et le nombre d’éléments à générer.

fill, fill_n, generate et generate_n

Les algorithmes de génération et d’initialisation sont déclarés de la manière suivante dans l’en-tête <algorithm> :

template <class ForwardIterator, class T> 
void fill(ForwardIterator premier, ForwardIterator dernier, const T &valeur); 

template <class OutputIterator, class T> 
void fill_n(OutputIterator premier, Size nombre, const T &valeur); 

tempalte <class ForwardIterator, class T, class Generator> 
void generate(ForwardIterator premier, ForwardIterator dernier, Generator g); 

template <class OutputIterator, class T, class Generator> 
void generate_n(OutputIterator premier, Size nombre, Generator g);

À savoir

Pour parcourir les éléments des conteneurs, les algorithmes utilisent les itérateurs.
ForwardIterator est un itérateur en-avant. Un itérateur en-avant est analogue à une vidéocassette – nous ne pouvons l’utiliser que dans un seul sens, mais il est possible de la lire indéfiniment. Ce type d’itérateur possède toutes les caractéristiques d’un itérateur d’entrée. Un itérateur en-avant est donc constructible par défaut, nous pouvons lui affecter une valeur et le comparer en égalité. Il est également possible de lui appliquer l’indirection et de l’incrémenter. Ce type d’itérateur fournit les deux accès en lecture et en écriture sur l’objet pointé.

OutputIterator est un itérateur de sortie. Il doit être constructible par défaut, et nous devons pouvoir lui attribuer une valeur. Cet itérateur garantit les accès en écriture – mais non les accès en lecture – sur l’objet pointé.

Code 9.1 : algorithme de génération et de stockage d’éléments dans un conteneur

#include <iostream> 
#include <list> 
#include <iterator>  
#include <algorithm>  

using namespace std; 

//Fonction de génération des valeurs à stocker 
int Generateur() 
{ 
   static int i = 0; 
   return i++; 
} 

int main() 
{ 
   typedef list<int> li; //li est le type liste d’entiers 
   li ma_liste;             //on crée une liste 
   //On l’alimente avec les 20 premiers entiers : 
   generate_n(back_inserter(ma_liste), 20, Generateur); 
   //On affiche la liste : 
   li::iterator i = ma_liste.begin(); 
   while (i != ma_liste.end())  
   { 
    cout << *i << endl; 
    i++; 
   } 
}


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

A voir également :

Ce document intitulé «  Manipulation de données - Initialisation et remplissage  » issu de CommentCaMarche (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.