A. La bibliothèque standard de patrons (templates) pour C++

La bibliothèque standard de patrons (STL) est une bibliothèque bibliothèque très répandue de code C++, développée par Silicon Graphics (www.sgi.com). Cette annexe donne un bref aperçu de ses fonctions principales, utilisées tout au long du code de Greenstone. Pour une description plus détaillée, consultez le manuel de référence officiel de STL, disponible en ligne sur le site webwww.sgi.com, ou l'un des nombreux manuels traitant de STL, tel que celui de Josuttis (1999).

Comme le suggère le mot «patron», STL n'est pas juste une bibliothèque d'objets prêts à l'emploi. Couplée avec le mécanisme de patrons de C++, elle fournit aux programmeurs une solution pour développer leurs propres objets de manière concise, objets qui tapent dans les fonctionnalités algorithmiques embarquées dans STL. Voilà qui ajoute une couche de complexité, mais cela en vaut la peine.

Pour aider à comprendre les extraits de code Greenstone donnés dans le présent manuel, nous donnons quelques exemples de STL à des fins de didacticiel.

A..1 Listes

#include <iostream.h>
 
#define nil 0
 
struct intlist {
   int val;
   struct intlist* next;
};
 
int total_int_list(intlist* head)
{
   int total = 0;
   intlist* curr = head;
   while (curr!=nil)
   {
       total += curr->val;
       curr = curr->next;
   }
 
   return total;
}
 
void main()
{
   intlist node1 = { 5, nil };
   intlist node2 = { 4, nil };
   node2.next = &node1;
 
   int total = total_int_list(&node2);
  cout << " List items total to: " << total << endl;
}

Étudions tout d'abord deux programmes qui implémentent une liste d'entiers. L'un utilise des types C++ de base (la «bonne vieille manière de faire»), tandis que l'autre utilise STL. La figure <imgref figure_programming_a_list_of_integers> montre le code source de l'implémentation qui n'utilisepasSTL. Les lignes 5-8 définissent les structures de données de base que nous allons utiliser: le champ val stocke la valeur de l'entier, et next (prochain) pointe vers le prochain élément de la liste – une implémentation classique d'une liste chaînée, en somme.

Pour illustrer l'utilisation de la structure de données, le programme principal (lignes 23-32) initialise une liste d'entiers avec les éléments [5, 4]. Il appelle ensuite la fonction total_int_list (total des entiers de la liste, définie lignes 10-21), fonction qui prend pour unique argument un pointeur vers la tête d'une liste et qui fait la somme de toutes les valeurs que la liste contient. La valeur renvoyée («9», dans notre cas) est affichée à l'écran.

Le gros du travail est accompli par les lignes 12-18. On commence par un peu d'initialisation: la variable locale total est mise à zéro, et curr (courant) pointe vers le début de la liste. Une boucle while ajoute ensuite l'élément entier courant au sous-total courant (total += curr→val;) avant de passer au prochain élément (curr = curr→next;). La boucle while termine quand curr vaut nil (vide), ce qui signifie qu'il ne reste plus aucun élément de la liste à traiter.

#include <iostream.h>
#include <list>

int total_int_list(list<int>* head)
{
   int total = 0;
   list<int>::iterator curr = head->begin();
   while (curr!=head->end())
   {
       total += *curr;
       curr++;
   }

   return total;
}

void main()
{
   list<int> vals;
   vals.push_back(5);
   vals.push_back(4);

   int total = total_int_list(&vals);
   cout << " List items total to: " << total << endl;
}

La figure <imgref figure_programming_a_list_of_integers_using_stl> montre un programme équivalent qui utilise STL. Il n'est plus nécessaire de définir une structure de données adéquate dans le code; seule la directive #include <list> de la ligne 2, qui inclut le patron de liste défini dans STL, est nécessaire. L'objet est appelé une «classe de contenance» car lors de la déclaration d'une variable de ce type on spécifie aussi le type qu'on souhaite qu'elle stocke. On réalise une liste d'entiers ligne 19 avec l'instruction list<int> vals;. On peut ajouter des éléments à l'objet en utilisant la fonction membre push_back(), comme dans les lignes 20-21.

Le gros du travail est accompli par les lignes 6-12. On commence toujours deux initialisations et une boucle while, mais à part cela la nouvelle syntaxe a fort peu en commun avec l'ancienne. Cette nouvelle manière de faire les choses gravite autour d'une variable de type iterator (itérateur, ligne 7). De nombreuses classes STL incluent des types iterator pour fournir une manière uniforme de traverser une suite d'objets de contenance. Le premier élément est renvoyé avec begin() (début) et l'élément qui suit le dernier élément est renvoyé avec end(). On passe à l'élément suivant par l'opération d'incrémentation ++, qui est surchargée par la classe d'itération pour implémenter cette tâche, et on accède à la valeur stockée par déréférenciation (*curr, ligne), opération elle aussi surchargée.

L'implémentation STL de ce programme est un peu plus concise que le code conventionnel (25 lignes, à comparer aux 31 originales). Les gains sont plus importants dans des projets plus volumineux, car l'objet list (liste) de STL est plus puissant que ce que cet exemple en illustre ici. C'est par exemple une liste doublement chaînée qui supporte diverses manières d'insérer et d'effacer – et il faudrait des efforts de programmation supplémentaires pour intégrer ces fonctionnalités à la version de liste d'entiers classique.

Remarquez que le paramètre total_int_list de la figure <imgref figure_programming_a_list_of_integers_using_stl> a été implémenté sous la forme d'un entier, pour correspondre au pointeur utilisé dans la variable total_int_list dans la figure <imgref figure_programming_a_list_of_integers>. En STL, il est souvent plus naturel (et plus souhaitable) d'utiliser des références plutôt que des pointeurs. Le paramètre devient alors list<int>& head, (tête), et ses fonctions membre sont appelées par la syntaxe head.begin(); (début de tête) et ainsi de suite.

A..2 Correspondances

Lorsque l'on implémente un système de bibliothèque numérique, il est utile de pouvoir stocker des éléments dans un tableau indicé par des chaînes de texte plutôt que par des nombres. Dans Greenstone, par exemple, ceci simplifie grandement le stockage des fichiers de macros après leur lecture; de même pour les divers fichiers de configuration. Un type de données qui permet un tel accès s'appelle untableau associatif, et les langages de programmation modernes de haut niveau en proposent souvent. On l'appelle aussi parfoistableau de hachage(surtout en Perl), puisque la technique habituelle d'implémentation d'un index de texte est de hacher (calculer une somme de contrôle) les valeurs du tableau associatif.

#include <iostream.h>
#include <map>
 
int total_int_table(map<char*, int>& table)
{
   int total = 0;
   map<char*, int>::iterator curr = table.begin();
   while (curr!=table.end())
   {
       total += (curr->second);
       curr++;
   }
 
   return total;
}
 
int main()
{
   map<char*, int> table;
   table["Alice"] = 31;
   table["Peter"] = 24;
   table["Mary"]   = 47;
 
   int total = total_int_table(table);
   cout << " Age total: " << total << endl;
  }

En STL, on fait des tableaux associatifs en utilisant l'objet map (carte, ou correspondance). La figure <imgref figure_using_associative_arrays_in_stl> présente un exemple quelque peu artificiel qui stocke l'âge de trois personnes (Alice, Pierre, et Marie) dans un tableau associatif indicé par leurs prénoms (lignes 19-22). Le problème est d'écrire une fonction qui calcule l'âge total de toutes les personnes présentes, sans savoir combien elles sont ni qui elles sont. Bien sûr, on pourrait résoudre ce problème avec un classique tableau d'entiers indicés numériquement. L'exemple est contraint d'illustrer les fonctionnalités de l'objet map et de mettre en valeur les similarités de traitement avec l'objet list équipé d'un iterator.

Tout comme list, map est une classe de contenance. Cependant, lorsque l'on déclare une variable de ce type, il faut spécifier deux¹⁾choses: le type d'index, et le type d'élément. Comme on peut le voir ligne 19, on obtient un tableau associatif qui stocke des entiers indicés par des chaînes en écrivant char* (c'est la manière de déclarer une chaîne en C++) en tant que type d'indiçage suivi de int en tant que type d'élément.

Il existe plusieurs manières de stocker des éléments dans le tableau associatif. Dans l'exemple, on utilise lignes 20-22 l'indice de tableau [ ], qui est surchargé, pour initialiser le tableau avec les âges des trois personnes. La ressemblance entre total_int_table – qui effectue le calcul principal dans le programme – et total_int_list de la figure <imgref figure_programming_a_list_of_integers> est frappante. Ces deux objets sont en fait presque identiques, et ce n'est pas une coïncidence. STL utilise lourdement l'héritage de sorte que des objets différents utilisent encore les mêmes opérations fondamentales. C'est particulièrement le cas des itérateurs (iterator). Les petites différences entre les deux fonctions sont que l'itérateur est maintenant tiré de map<char*, int>, et que l'accès à ses éléments se fait avec curr→second() – en effet la déréférenciation de la variable (*curr) est définie comme devant renvoyer un objet de type pair. Ceci enregistre à la fois le nom d'index (first, ou «premier») et la valeur de l'élément (second, ou «deuxième»), mais seul la deuxième nous intéresse. À part cela, le code est identique. La seule différence restante – le changement de l'unique argument de la fonction d'un pointeur vers une référence – est superficielle.

Greenstone utilise largement deux autres types STL: vector (vecteur), et set (ensemble). Le premier facilite les tableaux dynamiques, et le second supporte les opérations ensemblistes mathématiques telles que l'union, l'intersection, et la différence ensembliste.

¹⁾

Technically there are four types, but the last two are optional. Since we are only giving a basic introduction to this STL class, details about these last two types are omitted.

Greenstone Wiki

Table of Contents

A. La bibliothèque standard de patrons (templates) pour C++

A..1 Listes

A..2 Correspondances