Exemple d’un algorithme ‘numeric’ de la STL

STL contient plusieurs librairies, parmi une de celles-ci la librairie numérique offre plusieurs algorithmes pour le calcul numérique.  Nous présentons un exemple simple afin de calculer la moyenne en utilisant l’algorithme  “accumulate” de cette librairie.  Supposons que nous ayons à notre disposition un ensemble de données pour lesquelles nous voulons calculer la moyenne. Celles-ci peuvent être sous un format d’un vecteur, d’une list, d’un map, hash table, tableau pour nommer que ceux-ci. La moyenne pourrait être calculée de la manière suivante :

Pour plusieurs programmeurs utiliser des boucles est plus naturel que d’appeler un algorithme. Le pain et le beurre des algorithmes de la  STL c’est que plusieurs lignes de code qui sont faites  avec des boucles explicites du type ‘for’, ‘while’, pourraient aussi bien être écrites en utilisant les algorithmes. Regardons une nouvelle approche en utilisant l’algorithme numérique “accumulate” de la STL. 

Prototype
“Accumulate” est surchargé et possède 2 prototypes:

template <class InputIterator, class T>
T accumulate( InputIterator first, InputIterator last, T init);

template <class InputIterator, class T, class BinaryFunction>
T accumulate( InputIterator first, InputIterator last, T init, BinaryFunction binary_op);

Fonction template “accumulate” est une version généralisé de la sommation. L’algorithme initialise d’abord le résultat à ‘init’. Puis pour chacun des éléments (itérateur i) de l’ensemble [first,last[, en commençant par le début jusqu’à la fin, modifie celui-ci en utilisant ‘operator+’ result=result+*i (première version,) ou par une operation binaire ( result = binary_op (result, *i) (deuxième version). Cet algorithme a une complexité linéaire. Comme tous les algorithmes de la STL, “accumulate” prend comme arguments des itérateur pour spécifier la portion du containeur ou la totalité de celui-ci. Les algorithmes opèrent sur les conteneurs uniquement via les itérateurs. De cette façon les algorithmes peuvent être utilisés  par plusieurs types de containers. Ci-dessous la liste des fichiers d’en-tête pour notre exemple:

Le premier fichier d’en-tête  provient du nouveau C++11 pour le type “tuple”. Depuis C++11 un nouveau type a été introduit (une nouvelle fonctionnalité) appelé “tuple”.  Le type “tuple” est très similaire à celui de “pair ”, la principale différence entre les deux, “pair ” représente deux valeurs comme une seule. “Tuple” étend ce concept à un nombre arbitraire d’éléments (au minimum dix). Puis les deux fichiers d’en-tête suivant, ‘vector’ et ‘numérique’, correspondent à la collection (STL) que nous utilisons pour stocker le data et l’algorithme “accumulate” respectivement. Finalement nous utilisons des opérateurs d’initialisations de la librairie ‘Boost Assign Library’. Dans bien des cas, nous voulons tester sans avoir à utiliser un très grand nombre de données et être en mesure d’initialiser la collection rapidement. La STL ne  nous facilite pas la tâche pour ceci, Boost Assign Library fournit un ensemble d’outils ou d’opérateurs pour accomplir cette tâche. Nous allons écrire la fonction binaire qui a comme responsabilité de calculer les statistiques. D‘abord  nous définissons un “ typedef ” pour la lisibilité (un synonyme, pas un nouveau type).

Le premier argument de la fonction binaire est le “tuple” (type statsVar), celui-ci tient toute l’information pour compiler les statistiques et le second est l’élément que nous traversons (valeur de l’itérateur). Il est important de remarquer que le type ‘statsVar’ est retourné par la fonction, prêt pour le prochain élément (accumule l’information). Le corps de cette fonction est assez simple, d’abord on spécifie que nous utilisons le ‘namespace std’, ceci évite d’avoir à écrire le scope continuellement. Ensuite on utilise le ‘getter’, nouvelle fonctionnalité de C++11 pour mettre à jour les composantes du ‘tuple’ (‘typedef’ contient trois arguments). D’abord on incrémente le compteur à chaque élément visité, puis on ajoute l’élément courant à la somme compilée (pour faire la moyenne) et finalement la somme du carré pour éventuellement calculer la variance. Maintenant nous allons tester notre algorithme de statistique sur un ensemble de valeurs arbitraires.

D’abord on crée un vecteur de la STL de dix éléments que nous initialisons avec la méthode ‘reserve()’. Cette méthode alloue la mémoire pour le nombre d’éléments, on évite ainsi de faire des réallocations quand des éléments sont ajoutes dans le vecteur (couteux x quand  le vecteur est de grande taille), c’est une bonne pratique. Ensuite on assigne des valeurs numériques en utilisant l’opérateur ‘+=’ de la librairie ‘Boost Assign’. Permet un style d’initialisation sous forme de liste, très pratique quand  on a un petit nombre d’éléments.  Puis on calcule les statistiques par un appel de l’algorithme ‘accumulate’ en lui passant comme paramètre le vecteur (begin(), end()), la valeur initiale (make_tuple) et la fonction binaire ‘computeStats’. L’algorithme retourne le résultat compilé (accumulation après avoir visite tous les éléments de la collection). Finalement on affiche les statistiques en utilisant les “getter“.

La chose remarquable dans cet exemple, le code est concis et sans boucle ‘for’.
Les algorithmes de la STL offrent un niveau d’abstraction qui permet une implémentation très propre. Ceux-ci permettent d’appliquer une opération à un ensemble d’éléments sans avoir se préoccuper en détail de la nature de ces éléments, et sans avoir à implémenter un code laborieux et spécialisé pour le faire. Les algorithmes (et la STL plus généralement) proposent le meilleur compromis. Pourquoi?
Selon  Scott Meyers’s article “STL Algorithms vs. Hand-Written Loops, Dr. Dobbs’s October 2001” il est préférable d’utiliser des algorithmes aux boucles explicites pour les raisons suivantes:

• Efficacité : algorithme de la STL sont souvent plus efficace que les boucles explicites;
• Robustesse : écrire des boucles explicitement est sujet à des erreurs;
• Maintenabilité : code qui est plus facile à comprendre. Tout est gère par l’algorithme et compatible avec tous les types de containeur (qui supporte la stl-interface);

Cet exemple montre le degré d’abstraction de la STL d’être capable de manipuler des données d’un vecteur (stl-like container) et de les passer à l’algorithme afin  d’accomplir une tâche complexe.