Précédent

Index

Suivant

Chapitre 4 La généricité

La notion de généricité permet de définir des modules paramétrés par le type qu'ils manipulent. Un module générique n'est alors pas directement utilisable : c'est plutôt un patron de module qui sera ``instancié'' par les types paramètres qu'il accepte.

4.1 Les fonctions génériques

Supposons que l'on souhaite écrire une fonction min qui accepte deux paramètres et qui renvoie la plus petite des deux valeurs qui lui est fournie. On désire bénéficier de cette fonction pour certains types simples disponibles en C++ (int, char, float, double). La première solution pour atteindre ce but est d'utiliser la surcharge et de définir 4 fonctions min, une pour chacun des types considérés :

int min (int a, int b) {
  return ((a < b)? a : b);
}

float min (float a, float b) {
  return ((a < b)? a : b);
}

double min (double a, double b) {
  return ((a < b)? a : b);
}

char min (char a, char b) {
  return ((a < b)? a : b);
}

Lors d'un appel à la fonction min, le type des paramètres est alors considéré et l'implantation correspondante est finalement appelée. Ceci présente cependant quelques inconvénients :

La définition des 4 fonctions mène à des instructions identiques, qui ne sont différenciées que par le type des variables qu'elles manipulent. On s'aperçoit ici que plus qu'une fonction, on souhaiterait exprimer une méthode, valable pour n'importe quel type manipulé : la fonction min est la fonction qui renvoie le plus petit des paramètres qui lui est fourni. Cet élément est déterminé grâce à l'opérateur < qui établit une relation d'ordre sur le type d'élément considéré.
Si on souhaite étendre la définition de cette fonction à de nouveaux types, il faut définir une nouvelle implantation de la fonction min par type considéré.

Une autre solution est de définir une fonction générique, dite aussi en C++ fonction template. Cette définition définit en fait un patron de fonction, qui est instancié par un type de données (ici le type T) pour produire une fonction par type manipulé :

template <class T>
T min (T a, T b)
{
  return ((a < b)? a : b);
}

int main()
{
  int a = min(10, 20);         // int min(int, int)
  float b = min(10.0, 25.0);   // float min(float, float)
  char c = min('a', 'W');      // char min(char, char)
}

Il n'est donc plus nécessaire de définir une implantation par type de données. De plus, la fonction min est valide avec tous les types de données dotés de l'opérateur <. On définit donc bien plus qu'une fonction, on définit une méthode permettant d'obtenir une certaine abstraction en s'affranchissant des problèmes de type. Quelques remarques :

Il est possible de définir des fonctions template acceptant plusieurs types de données en paramètre. Chaque paramètre désignant une classe est alors précédé du mot-clé class, comme dans l'exemple : template <class T, class U> ....
Chaque type de données paramètre d'une fonction template doit être utilisé dans la définition de cette fonction.
Pour que cette fonctionnalité soit disponible, les fonctions génériques doivent être définies dans des fichiers d'interface (headers)¹. Les fonctions template sont en effet expansées elles aussi. Ainsi, chaque appel fait à ce genre de fonctions est remplacé, à la précompilation, par le code source correspondant à la fonction.

4.2 Les classes génériques

Il est également possible de définir des classes génériques ou template, c'est-à-dire paramétrées par un type de données. Cette technique évite ainsi de définir plusieurs classes similaires pour décrire un même concept appliqué à plusieurs type de données différents. Elle est largement utilisée pour définir tous les types de containers (comme les listes, les tables, les piles, etc.), mais aussi des algorithmes génériques par exemple.

La syntaxe permettant de définir une classe générique est similaire à celle qui permet de définir des fonctions génériques. Ainsi, la classe Point est un exemple de classe générique, portant sur des points dont la précision de représentation (à partir d'entiers, de réels, etc.) est le type paramètre de la classe :

template <class T>
class Point {
protected:
  T _x;      // Abcisse
  T _y;      // Ordonnée

public :
  // Constructeur par défaut
  Point() : _x(0), _y(0) {}

  // Constructeur
  Point(T x, T y) : _x(x), _y(y) {}

  // Accès à x
  const T x() const {return _x;}

  // Accès à y
  const T y() const {return _y;}

  // Translation
  void translation(T x, T y);
};

template <class T> void
Point<T>::translation(T x, T y)
{
  _x += x;
  _y += y;
}

On peut ensuite utiliser cette classe en instanciant le type générique :

#include "Point.H"

int main()
{
  Point<int> pointEntier(2, 3);
  Point<float> pointReel(3.14, 2.27);
  
  pointReel.translation(pointEntier.x(), pointEntier.y());
}

Quelques remarques :

Comme dans le cas des fonctions génériques, tout le code source correspondant à des classes génériques (y compris la définition de leurs méthodes) doit se trouver dans l'interface de la classe correspondante.
Une classe générique permet de définir des attributs, des paramètres ou des valeurs de retour de méthodes génériques. De façon réciproque, pour pouvoir définir des entités génériques à l'intérieur d'une classe, la classe doit elle-même être générique.
Attention à la syntaxe des méthodes génériques définies en dehors du corps de la classe. La définition se fait de la manière suivante :

template <class T> typeRetour nomClasse<T>::nomMéthode(liste_paramètres)

Voir par exemple ci-dessus la définition de la méthode translation de la classe générique Point.

4.3 La bibliothèque STL

La bibliothèque Stl (Standard Template Library²) est certainement l'un des atouts de C++. Cette bibliothèque fournit un ensemble de composants C++ bien structurés qui marchent de façon cohérente et peuvent aussi être adaptés facilement. En effet, il est possible d'utiliser les structures de données proposées par Stl avec des algorithmes personnels, les algorithmes de la bibliothèque avec des structures de données personnelles, ou d'utiliser toutes les composantes Stl ! Lors de sa conception, l'accent a été mis sur l'efficacité et sur l'optimisation des composants, ce qui en fait un outil très puissant.

Il faut bien noter que la Stl est fondée sur la séparation entre données et opérations. De ce point de vue, on peut considérer qu'elle contredit conceptuellement l'un des grands axiomes de la programmation objet, à savoir l'encapsulation dans une même entité des données et des opérations qui les manipulent ! Il faut en fait voir la généricité comme une approche ``orthogonale'' à l'approche objet classique.

Ce chapitre présente les généralités liées à Stl. Pour en tirer pleinement partie, une bonne documentation s'avère nécessaire. Un des meilleurs ouvrages de référence de cette bibliothèque est celui de Musser & Saini [8]. On consultera aussi de manière utile d'autres références comme le livre de Josuttis [3] qui traite de l'ensemble de la bibliothèque C++, ou le livre de Meyers dédié à la STL [7].

La Stl contient cinq types de composants : des containers, des itérateurs, des algorithmes, des objets-fonctions et des adaptateurs. Nous nous intéressons dans ce chapitre aux trois premiers composants.

4.3.1 Les containers

Les containers sont des objets qui permettent de stocker d'autres objets. Ils sont décrits par des classes génériques représentant les structures de données logiques les plus couramment utilisées : les listes, les tableaux, les ensembles... Ces classes sont dotées de méthodes permettant de créer, de copier, de détruire ces containers, d'y insérer, de rechercher ou de supprimer des éléments. La gestion de la mémoire, c'est-à-dire l'allocation et la libération de la mémoire, est contrôlée directement par les containers, ce qui facilite leur utilisation. L'exemple suivant présente une application où les valeurs entières saisies par un utilisateur sont stockées dans une liste et dans un tableau :

#include <iostream>
#include <vector>
#include <list>

int main()
{
  vector<int> tableauEntiers;  // Crée un tableau d'entiers vide
  list<int> listeEntiers;      // Crée une liste d'entiers vide
  int unEntier;

  // Saisie des entiers
  cout << "Saisir le prochain entier (-1 pour finir) : ";
  cin >> unEntier;

  while (unEntier != -1) {
    tableauEntiers.push_back(unEntier);
    listeEntiers.push_back(unEntier);

    cout << "Saisir le prochain entier (-1 pour finir) : ";
    cin >> unEntier;
  }

  // Nombre d'éléments des containers
  cout << "Il a y " << tableauEntiers.size()
       << " éléments dans le tableau" << endl;

  cout << "Il a y " << listeEntiers.size()
       << " éléments dans la liste" << endl;
  
  // Accès à des éléments
  cout << "Premier élément du tableau : "
       << tableauEntiers.front() << endl;

  cout << "Premier élément de la liste : "
       << listeEntiers.front() << endl;

  int milieu = tableauEntiers.size() / 2;

  cout << "Élément de milieu de tableau : "
       << tableauEntiers[milieu] << endl;
}

Voici un exemple d'exécution de ce programme :

Saisir le prochain entier (-1 pour finir) : 4
Saisir le prochain entier (-1 pour finir) : 5
Saisir le prochain entier (-1 pour finir) : 3
Saisir le prochain entier (-1 pour finir) : 7
Saisir le prochain entier (-1 pour finir) : 6
Saisir le prochain entier (-1 pour finir) : 3
Saisir le prochain entier (-1 pour finir) : -1
Il a y 6 éléments dans le tableau
Il a y 6 éléments dans la liste
Premier élément du tableau : 4
Premier élément de la liste : 4
Élément de milieu de tableau : 7

Quelques remarques sur les containers et sur l'exemple présenté :

Un certain nombre de méthodes sont disponibles sur tous les types de containers, ce qui permet d'homogénéiser leur utilisation. C'est le cas par exemple de la méthode push_back qui insère un nouvel élément à la fin d'un container.
D'autres méthodes ou opérateurs sont disponibles en fonction du type de container utilisé. L'opérateur [] est disponible sur les objets de type vector, mais pas sur ceux de type list : il permet d'accéder directement à un élément. Plus de précisions sur ces méthodes sont disponibles au § B.1.
L'utilisateur n'a pas à se soucier de l'allocation ou de la libération de la mémoire. C'est vrai lors de l'insertion d'éléments et aussi à la fin du programme : aucune instruction particulière n'est nécessaire pour restituer la mémoire occupée par les containers. À la sortie du bloc dans lequel ils sont définis, leur destructeur se charge de libérer toutes les ressources occupées.
Les containers peuvent manipuler n'importe quel type de données, à partir du moment où la classe correspondante est dotée d'un certain nombre de méthodes nécessaires à Stl (pour une classe X) :
- X() : un constructeur par défaut,
- X(const X&) : un constructeur par copie,
- operator=(const X&) : l'opérateur d'affectation,
- operator==(const X&) : l'opérateur d'égalité,
- operator<(const X&) : l'opérateur inférieur (utile uniquement pour les tris).
Ainsi, un type bien défini pour être manipulable dans un container comprendra au minimum les éléments suivants :
```
  class MonType {
      // Mettre ici données privées et protégées 
  public: 
      // Constructeurs indispensables 
      MonType();
      MonType(MonType const&); 
      // + autres constructeurs éventuels 

      // Le destructeur -- ne pas oublier virtual 
      // si MonType peut avoir des sous-classes
      virtual ~MonType();
    
      MonType& operator=(MonType const&);
      bool operator==(MonType const&) const;
      bool operator<(MonType const&) const; 
      // autres méthodes et opérateurs ...  
  };
```

Les différentes sortes de containers disponibles sont :

vector : container implantant les tableaux, qui autorise les accès directs sur ses éléments. Les opérations de mise à jour (insertion, suppression) sont réalisées en un temps constant à la fin du container, et en un temps linéaire (dépendant du nombre d'éléments) aux autres endroits.
list : container implantant les listes doublement chaînées, dédié à la représentation séquentielle de données. Les opérations de mise à jour sont effectuées en un temps constant à n'importe quel endroit du container.
deque : container similaire au vector, effectuant de plus les opérations de mise à jour en début de container en un temps constant.
set : container implantant les ensembles où les éléments ne peuvent être présents au plus qu'en un seul exemplaire.
multiset : container implantant les ensembles où les éléments peuvent être présents en plusieurs exemplaires.
map : container implantant des ensembles où un type de données appelé clé est associé aux éléments à stocker. On ne peut associer qu'une seule valeur à une clé unique. On appelle aussi ce type de container tableau associatif.
multimap : container similaire au map supportant l'association de plusieurs valeurs à une clé unique.
stack : adaptateur permettant de donner à un container le comportement d'une pile, c'est-à-dire que le premier élément qui entre est le dernier qui sort.
queue : adaptateur permettant de donner à un container le comportement d'une file, c'est-à-dire que le premier élément qui entre est aussi le premier qui sort.
priority_queue : adaptateur permettant de donner à un container le comportement d'une file avec priorités, une variante de la file où certains éléments peuvent avoir des priorités supplémentaires à d'autres pour sortir de la file.

Une carte de référence sur les containers existants et sur les méthodes dont ils sont dotés est disponible à l'annexee B.

4.3.2 Les itérateurs

Les itérateurs sont une généralisation des pointeurs, ce qui permet au programmeur de travailler avec des containers différents de façon uniforme. Ils permettent de spécifier une position à l'intérieur d'un container, peuvent être incrémentés ou déréférencés (à la manière des pointeurs utilisés avec l'opérateur de déréférencement '*') et deux itérateurs peuvent être comparés. Tous les containers sont dotés d'une méthode begin qui renvoie un itérateur sur le premier de leurs éléments, et d'une méthode end qui renvoie un itérateur sur une place se trouvant juste après le dernier de leurs éléments. On ne peut ainsi pas déréférencer l'itérateur renvoyé par la méthode end. Voici un exemple d'utilisation des itérateurs :

#include <iostream>
#include <list>

int main()
{
  list<int> lesEntiers;

  // Ici, des instructions pour initialiser la
  // liste des entiers

  ...

  // Affichage des éléments contenus dans la liste

  list<int>::iterator it;

  for (it = lesEntiers.begin(); it != lesEntiers.end(); it++)
    cout << *it << endl;
}

Ces itérateurs sont dotées de méthodes permettant de les manipuler (cf. § B.2). Il existe une hiérarchie d'itérateurs, qui n'est pas liée à un quelconque héritage :

Les itérateurs d'entrée (input iterators) : ils permettent d'accéder séquentiellement à des sources de données. Cette source peut-être un container, un flot.
Les itérateurs de sortie (output iterators): ils permettent de préciser la localisation d'une destination permettant de stocker des données. Cette source peut-être un container, un flot.
Les itérateurs à sens-unique (forward iterators) : ils sont dotés de toutes les méthodes des itérateurs d'entrée et de sortie. Ils sont utilisés pour parcourir séquentiellement une séquence de données dans un sens. Ils ne peuvent pas être utilisés pour effectuer des retours en arrière.
Les itérateurs à double-sens (bidirectional iterators) : ils sont dotés de toutes les méthodes des itérateurs à sens-unique. Ils sont également utilisés pour effectuer des parcours séquentiels de données, qu'ils peuvent effectuer dans les deux sens.
Les itérateurs à accès direct (random-access iterators) : ils sont dotés de toutes les méthodes des itérateurs à double-sens. Ils permettent d'accéder directement à des valeurs contenues dans un container, sans être obligé d'y accéder séquentiellement.

Tous les containers disponibles sous Stl fournissent au moins des itérateurs à double-sens, et certains fournissent des itérateurs à accès direct (cf. § B.1) pour les itérateurs par défaut renvoyés par chaque type de container.

4.3.3 Les algorithmes

Les algorithmes sont des fonctions C++ génériques qui permettent d'effectuer des opérations sur les containers. Afin de pouvoir s'appliquer à plusieurs types de containers, les algorithmes ne prennent pas de containers en arguments, mais des itérateurs qui permettent de désigner une partie ou tout un container. De ce fait, il est même possible d'utiliser ces algorithmes sur des objets qui ne sont pas des containers. On peut par exemple utiliser un istream_iterator (cf. § B.2) comme paramètre d'un algorithme, qui va alors s'appliquer à l'entrée standard. Certains algorithmes ne nécessitent que des itérateurs de base (d'entrée ou de sortie), et d'autres nécessitent des itérateurs plus évolués, comme la fonction sort³ (effectuant un tri) qui nécessite un itérateur à accès direct.

Les algorithmes disponibles sont décrits en annexe B.3. Pour les utiliser, il suffit d'inclure l'en-tête algorithm. Un exemple d'utilisation des algorithmes est présenté ci-dessous :

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
  vector<int> tableauEntiers;  // Crée un tableau d'entiers vide
  int unEntier;

  // Saisie des entiers

  cout << "Saisir le prochain entier (-1 pour finir) : ";
  cin >> unEntier;

  while (unEntier != -1) {
    tableauEntiers.push_back(unEntier);

    cout << "Saisir le prochain entier (-1 pour finir) : ";
    cin >> unEntier;
  }

  // Tri du tableau

  sort(tableauEntiers.begin(), tableauEntiers.end());
  
  // Affichage des éléments triés

  vector<int>::iterator it;

  for (it = tableauEntiers.begin(); it != tableauEntiers.end(); it++)
    cout << *it << " ";

  cout << endl;
}

Voici le résultat produit à partir de cet exemple :

Saisir le prochain entier (-1 pour finir) : 5
Saisir le prochain entier (-1 pour finir) : 3
Saisir le prochain entier (-1 pour finir) : 8
Saisir le prochain entier (-1 pour finir) : 10
Saisir le prochain entier (-1 pour finir) : 3
Saisir le prochain entier (-1 pour finir) : 6
Saisir le prochain entier (-1 pour finir) : 9
Saisir le prochain entier (-1 pour finir) : -1
3 3 5 6 8 9 10

4.4 Programmer avec la STL

Le bon usage de la STL nécessite une remise en cause de beaucoup d'habitudes prises en programmation plus traditionnelle. On se reportera avec profit au livre de Meyers [7], par exemple, pour apprendre à tirer le maximum de profit de la puissance de cette approche générique. Voici très simplement quelques conseils succincts tirés de ce livre, auquel on se référera pour les détails :

Pour tester si un container est vide, utiliser empty() au lieu de regarder la taille du container avec la méthode size().
Préférer les fonctions membres travaillant sur un intervalle aux fonctions travaillant élément par élément.
Préférer vector et string aux tableaux alloués dynamiquement.
Utiliser reserve pour éviter les réallocations inutiles.
Les méthodes de comparaison doivent toujours retourner false pour des valeurs égales.
Faire suivre les algorithmes ou méthodes remove_* par erase si on veut vraiment effacer les objets et pas seulement les déplacer.
Préférer les appels à des algorithmes aux boucles manuelles du genre for ou while.
Préférer les fonctions membres aux algorithmes de même nom, quand on a le choix.

4.5 Quelques utilitaires de la bibliothèque standard

Mis à part la Stl à proprement parler, la bibliothèque standard de C++ fournit un grand nombre de fonctionnalités plus générales. Nous en citons quelques-unes seulement ; le lecteur qui voudra une vision complète des ressources de la bibliothèque pourra se référer à un livre de référence tel que celui de Josuttis [3], ou à de l'information en ligne comme par exemple à l'adresse http://www.cplusplus.com/.

4.5.1 Les paires

La classe pair fournit un moyen générique de traiter une paire de valeurs comme une entité unique. Les classes de containers map et multimap utilisent en particulier des paires pour gérer les couples clé/valeur.

La fonction générique make_pair permet de créer une paire à partir de deux valeurs ; ainsi, on pourra écrire :

  map<int, string> codesPostaux;

  // ...

  codesPostaux.insert(make_pair(54000, "Nancy"));

On accède respectivement à la première et à la deuxième valeur d'une paire par les variables first et second. Ainsi, en gardant l'exemple courant, on peut parcourir la map codePostaux par un itérateur et accéder comme suit aux valeurs associées :

  map<int, string>::iterator it = codesPostaux.find(54280);

  if (it != codesPostaux.end())
      cout << (*it).first << " - " << (*it).second;

À noter au passage la notation pour accéder aux éléments ou méthodes d'un objet ``pointé'' par l'itérateur. En fait, les compilateurs les plus récents permettent d'utiliser la notation plus naturelle (pour un programmeur C ou C++) it->first, mais les compilateurs plus anciens ne l'autorisent pas.

4.5.2 Opérateurs de comparaison supplémentaires

Nous avons vu que pour manipuler un type avec des containers, celui-ci doit comporter la définition des opérateurs < et ==. Le fichier header utility définit l'espace de noms rel_ops avec les opérateurs génériques suivants :

  namespace std {
    namespace rel_ops {
      template <class T>
      inline bool operator!= (const T& x, const T& y) {
        return !(x == y);
      }

      template <class T>
      inline bool operator> (const T& x, const T& y) {
        return y < x;
      }

      template <class T>
      inline bool operator<= (const T& x, const T& y) {
        return !(y < x);
      }

      template <class T>
      inline bool operator>= (const T& x, const T& y) {
        return !(x < y);
      }
    }
  }

Ainsi, en utilisant le namespace std::rel_ops on disposera pour tout type bien défini de l'ensemble des opérateurs de comparaison classiques.

4.5.3 La classe `string`

La bibliothèque standard de C++ définit le type générique basic_string ainsi que ses instanciations standard string et wstring. Ce dernier permet d'utiliser des jeux de caractères plus étendus que ce qu'on peut faire avec le type standard char, par exemple Unicode ou des jeux de caractères asiatiques.

Nous nous contentons de donner dans la figure 4.1 un aperçu des opérations disponibles les plus courantes sur une chaîne de caractères.

Opération Effet

Constructeurs

string s Crée une chaîne vide

string s(str) Crée une copie de str

string s(beg,end) Crée une chaîne initialisée par les caractères que l'on trouve entre les itérateurs beg et end

etc. il y a beaucoup d'autres constructeurs que nous ne détaillons pas ici

=, assign() Affectation

+=, append(), push_back() Concaténation de caractères

+ Concaténation de chaînes

==, !=, <, etc. Comparaisons de chaînes

clear() Efface tous les caractères (la chaîne devient vide)

empty() Teste si la chaîne est vide

size(), length() Taille de la chaîne (nombre de caractères)

[], at() Accède à un caractère donné par son indice dans la chaîne

data() Donne un tableau de caractères construit à partir de la chaîne

substr() Extraction de sous-chaînes

begin(), end() Fournit un accès de type itérateurs sur une chaîne ; de ce fait, on peut parcourir une chaîne comme on parcourt un container, et utiliser les algorithmes génériques de la Stl sur les chaînes

Fonctions de recherche

find() Trouve la première occurrence d'un caractère

rfind() Trouve la dernière occurrence d'un caractère

find_first_of() Trouve la première occurrence d'un des caractères de la chaîne donnée en paramètre

etc.

Figure 4.1 : Opérations les plus courantes de la classe string.

4.6 Autres bibliothèques

La bibliothèque standard n'a pas vocation à contenir l'ensemble des fonctionnalités dont vous pouvez avoir besoin. Elle représente uniquement les fonctionnalités de base sur lesquelles le comité de normalisation de C++ est parvenu à un accord. Il existe de très nombreuses bibliothèques complémentaires, offrant des services dans un ensemble de domaines généraux ou spécifiques.

Une mention particulière peut être donnée à Boost⁴ qui est un ensemble de bibliothèques répondant à des besoins généraux (gestion de graphes, par exemple) mais qui n'ont pas fait l'objet d'un consensus assez général pour être incluses dans la biblothèque standard. Ces bibliothèques n'en représentent pas moins des ensembles stables et robustes de fonctionnalités et je ne peux que vous encourager à aller voir si vous y trouvez les fonctions et classes dont vous avez besoin, avant de décider de les implanter vous-mêmes.

1: Les fonctions inline et template sont ainsi les seules fonctions à être définies dans les interfaces. Toutes les autres sont définies dans les fichiers d'implantation (.cpp) et sont seulement déclarées dans les interfaces.
2: Bibliothèque standard générique.
3: Du coup, cet algorithme n'est pas applicable sur les listes qui ne fournissent que des itérateurs à double sens. C'est pour cette raison que la classe list est dotée d'une méthode sort.
4: http://www.boost.org/.

Précédent

Index

Suivant