Programmation générique et templates

De manière plus générale, on devrait parler de programmation générique. Les templates sont l'implémentation C++ du concept, mais Java offre une version légèrement moins puissante du concept (les Genericsversion PDF) depuis la version 5, et C# fait de même depuis sa version 2

Ce document se veut une description opérationnelle de ce qu'est un modèle, ou template, en C++. Vous remarquerez que le thème des templates ne constitue pas tant un sujet orienté objet (OO) qu'un thème en partie orthogonal: le développement de classes et d'algorithmes dont les types sont paramétriques. Combiner les deux idées permet une généralisation rien de moins que fabuleuse.

Vous noterez que la possibilité de surcharger des opérateurs devient presque une nécessité si on veut être en mesure d'arriver à un concept aussi élégant que celui des templates.

C'est un peu à contrecoeur que j'utiliserai le terme anglais template dans ce document; l'équivalent français (modèle) est un peu galvaudé[1], ce qui risquerait (à mon avis) d'introduire de la confusion dans la texte.

Voir aussi http://www.boost.org/more/generic_programming.html pour une discussion intéressante de la programmation générique en C++. Pour une explication de certains détails techniques quant aux templates, je vous invite à lire le court mais très intéressant article http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1996/N0885.pdf.

Aussi, voir cet article qui explore à sa façon le sujet.

L'idée derrière les templates

Les templates sont d'abord et avant tout des types paramétriques. L'idée de types paramétriques date de bien avant la première norme ISO (1998), à partir de laquelle elle fit son entrée dans le standard officiel du langage, mais n'avait pas été bien testée et validée auparavant. Le concept est délicat, et son implantation devait être solide.

C++ est un langage dit fortement typé. Comme la plupart des langages orientés objet, avec des hiérarchies de classes, le contrôle strict des types y est primordial. Il existe des opérations relativement élémentaires qui s'implantent très mal dans ce contexte.

En fait, la fonction proposée à droite (aussi pénible en C qu'en C++, d'ailleurs) est un cas concret et commun de fonction simple qui ne s'implante pas proprement.

int a = 3, b = 5, c;
c = min(a, b);
Attention : ici, le mot impossible dans le commentaire à droit de l'appel signifie impossible à implanter sous forme de fonction pour tous les types. En effet, en langage C, on ne peut rédiger deux fonctions ayant le même nom mais des paramètres différents, en type ou en nombre. En C++, il est possible – et essentiel – qu'on puisse le faire.

On ne peut donc pas avoir, en langage C, les deux fonctions suivantes dans le même programme.

int min(int a, int b) {
   int resultat;
   if (a < b)
      resultat = a;
   else
      resultat = b;
   return resultat;
}
float min(float a, float b) {
   float resultat;
   if (a < b)
      resultat = a;
   else
      resultat = b;
   return resultat;
}

En langage C++, on peut y arriver. Toutefois, si on veut vraiment avoir une fonction min(a,b) qui fonctionne pour chaque type pertinent, il faut écrire la fonction propre à chacun de ces types. Or, on parle à chaque fois du même code, où seuls les types de données impliqués changent.

La solution traditionnelle, en langage C comme en langage C++, était d'avoir recours à une macro. Les macros étant sous la responsabilité du préprocesseur, elles consistent en un simple remplacement lexical (et paramétrique) dans le code.

Ainsi, on écrivait...
#define min(a,b) (((a)<(b))?(a):(b)) 
...ce qui signifie que le code suivant... ...devenait, une fois complétée la tâche du préprocesseur...
int main() {
   int i1 = 3, i2 = 5, i3;
   float f1 = 12.5f, f2 = -27.3f, f3;
   i3 = min (i1, i2);
   f3 = min (f1, f2);
}
int main() {
   int i1 = 3, i2 = 5, i3;
   float f1 = 12.5f, f2 = -27.3f, f3;
   i3 = (((i1)<(i2))?(i1):(i2));
   f3 = (((f1)<(f2))?(f1):(f2));
}

Ceci devenait donc la méthode passe-partout de contourner les contraintes de type du langage. Mais il y avait des risques (graves) à cette façon de faire. Le préprocesseur altère le code de manière lexicale; il n'a pas (ou, à vrai dire, n'a que très peu) d'intelligence propre au langage lui-même, et n'a surtout pas d'intelligence propre aux types.

Ainsi, la ligne proposée à droite passe sans peine l'étape du préprocesseur mais n'a aucun sens en langage C et ne passe donc pas l'étape du compilateur. De plus, les macros, ça finit par donner du code carrément épouvantable à déboguer.

int *p = min("Allo toi!",22);

La solution template offre le contrôle des types tout en permettant une fonction qui :

Pour rédiger un template de la fonction min(), il faut en analyser la fonctionnalité attendue. Ici, on désire une fonction qui :

  • recevra en paramètre deux objets du même type (deux int,deux float, deux string si on vise une comparaison lexicographique, etc.);
  • vérifiera, à l'aide de l'opérateur < défini sur ce type, lequel des deux est le plus petit;
  • affectera à une variable temporaire du même type, à l'aide de l'opérateur = défini sur ce type, la valeur du plus petit des deux;
  • retournera cette variable temporaire – il faudra donc que la fonction soit du même type que ses paramètres.

Si on considère cette analyse, il n'y a en tout temps qu'un seul type d'utilisé[2]. C'est précisément de ce type que nous voulons faire abstraction, tout en conservant la fonctionnalité derrière la fonction min().

Ainsi, le principe de la fonction min() serait celui qu'on voit décrit à droite. Attention, ceci n'est pas la syntaxe exacte d'un template en C++.

On y constate que si on nomme T le type utilisé, on conserve précisément la fonctionnalité voulue.

Dans la mesure où les différents objets se conforment à la règle selon laquelle ils sont tous du même type – et dans la mesure où les opérateurs < et = sont définis sur ce type, ce que le compilateur vérifie de façon routinière – le modèle suffit à décrire la fonction voulue.

T min (T a, T b)
   //
   // notez que normalement, en pseudocode, on
   // omettra les déclarations de variables et
   // les types impliqués, mais ici, c'est ce que
   // nous voulons mettre en évidence alors...
   //
   T résultat;
   Si a < b
      résultat ← a
   Sinon
      résultat ← b
   Retourner résultat;

Éléments de syntaxe

template<class T>
   T min(T a, T b) {
      T resultat;
      if (a < b)
         resultat = a;
      else
         resultat = b;
      return resultat;
   }

La syntaxe exacte de l'implantation par template de la fonction min() est telle que proposé à droite.

Notez tout particulièrement les éléments suivants :

Le programme suivant est un exemple complet de déclaration et d'utilisation d'une fonction template simple :

template<class T>
   T min(T a, T b)
   {
      T resultat;
      if (a < b)
         resultat = a;
      else
         resultat = b;
      return resultat;
   }
int main()
{
   int i1 = 3, i2 = 5, i3;
   float f1 = 12.5f, f2 = -27.3f, f3;
   i3 = min(i1, i2); // min() entre deux int, retourne un int
   f3 = min(f1, f2); // min() entre deux float, retourne un float
}

Avec prototypes, on obtiendra ce qui suit :

template<class T>
   T min(T, T);
int main()
{
   int i1 = 3, i2 = 5, i3;
   float f1 = 12.5f, f2 = -27.3f, f3;
   i3 = min(i1, i2);
   f3 = min(f1, f2);
}
template<class T>
   T min(T a, T b)
   {
      T resultat;
      if (a < b)
         resultat = a;
      else
         resultat = b;
      return resultat;
   }

Idée de contrat

Notez que ce qui suit prend le terme « contrat » dans une acception très générale, mais ce terme pourrait prendre une acception plus technique à partir de C++ 17. Prenez soin de ne pas confondre mon acception générale avec une acception formelle.

Exprimer un algorithme ou une classe sous forme générique implique la réalisation d'opérations sur des types génériques. Ces opérations présument certaines particularités de ces types, particularités qui varieront d'un algorithme à l'autre. On peut par exemple penser à :

Ces contraintes qui doivent être respectées par tout type auquel s'appliquera un algorithme générique donné constituent le contrat de cet algorithme.

Si on prend à titre d'exemple l'algorithme générique proposé à droite (version A), le contrat de T est très simple: il doit être possible de lui appliquer l'opérateur - unaire (donc à un seul opérande).

// version A
template <class T>
   void inverser_signe(T &obj) {
      obj = -obj;
   }

La version B impose un contrat différent: il doit être possible d'appliquer à T l'opérateur *= prenant comme opérande de droite un entier signé.

// version B
template <class T>
   void inverser_signe(T &obj) {
      obj *= -1;
   }

Le contrat de T pour la version C de l'algorithme est qu'il doit être possible d'appliquer à T l'opérateur * prenant comme opérande de droite un entier signé et que le résultat de cette opération doit pouvoir être affecté à un T à l'aide de l'opérateur =.

// version C
template <class T>
   void inverser_signe(T &obj) {
      obj = obj * -1;
   }

La version D impose encore un autre contrat: T doit offrir un constructeur par copie (utilisé deux fois, soit une pour le passage du paramètre par valeur et une autre pour générer la valeur de retour) et on doit aussi être capable de lui appliquer l'opérateur - unaire.

C'est là, soit dit en passant, la version généralement la plus rapide des quatre.

// version D
template <class T>
   T inverser_signe(T obj) {
      return -obj;
   }

Mettre en place un algorithme générique implique de clarifier par une documentation rigoureuse (et des commentaires clairs) les règles selon lesquelles on peut déterminer si un type peut y être utilisé ou non.

Détails d'implantation

Derrière chaque ajout au langage C++, on trouve des préoccupations d'efficacité en temps et en espace. Il fallait que les types paramétriques offrent un niveau de performance équivalent (ou supérieur) à celui des types non paramétriques, et que leur coût en espace soit aussi petit que possible.

Dans le cas d'un template, qui doit être compilé si on veut qu'il soit d'exécution rapide, il est impossible de connaître a priori toutes les utilisations possibles – toutes les combinaisons de types – qu'on puisse en faire. Aussi, le code propre à une utilisation précise (une combinaison de types spécifique) de template ne sera généré que si au moins une utilisation en est faite.

Dans le cas de notre exemple plus haut, le compilateur aura généré le code pour float min(float,float); et pour int min(int,int);, mais pas pour const string& min(const string&,const string&);.

template<class T, int i>
   class Tampon {
      T donnees[i];
      int taille;
   public:
      Tampon() : taille{i} {
      }
      // ...
   };

Il est possible de combiner des types paramétriques et des types non paramétriques dans une même unité de code. Par exemple, le code proposé ci-contre déclare une classe Tampon contenant un tableau de type paramétrique T de i (un entier) éléments.

Si on a cette déclaration de la classe paramétrique Tampon, on peut ensuite se déclarer des instances de Tampon de différents types.

Par exemple, observons le programme suivant qui déclare bf comme étant un Tampon de 20 float et bs comme étant un Tampon de 15 string :

Une fois déclarées, ces instances de Tampon peuvent être utilisées comme l'est n'importe quel objet, dans la mesure où les types impliqués sont respectés.

#include "tampon.h"
#include <string>
int main() {
   using std::string;
   Tampon<float,20> bf;
   Tampon<string,15> bs;
   // ...
}

Exemples typiques d'utilisation de templates de fonctions et de classes

Quelques cas où des templates s'avèrent tout désignés

Les fonctions min(a,b) et max(a,b), qui retournent respectivement le plus petit d'entre a et b et le plus grand d'entre a et b. Ces deux templates s'appliquent pour tous les types sur lesquels sont définis les opérateurs < et > et qui exposent un constructeur de copie.

La fonction swap(a,b), qui échange le contenu de a et de b.

Sans surprises, dû à l'utilité (et à l'ubiquité!) de ces fonctions, elles sont définies dans le standard (espace nommé std), dans <utility> ou dans <algorithm>. Utilisez les versions standards plutôt que des versions maisons sauf dans des cas extrêmes d'incompatibilité; elles sont susceptibles d'être optimisées au-delà de ce que vous auriez pu prévoir dans des exemples académiques (et oui, il est possible d'optimiser std::swap(), et oui, ça en vaut la peine!).

template<class T>
   T min(T a, T b) {
      return a < b? a : b;
   }
template<class T>
   T max(T a, T b) {
      return a > b? a : b;
   }
template<class T>
   void swap(T &a, T &b) {
      T temp = a;
      a = b;
      b = temp;
   }

Une classe Pile, qui permet d'empiler et de dépiler des objets de même type, implantée à l'aide d'un tableau.

Le code à droite présente à la fois une classe permettant de créer une pile de type paramétrique, avec un nombre maximum d'éléments pouvant être spécifié à la déclaration (100 par défaut).

Notez que dans ce cas, il existe une alternative intéressante aux templates, qui lui est supérieure à certains égards et inférieure à d'autres points de vue. Cette alternative relève des mécanismes de polymorphisme.

Joindre le polymorphisme, qui permet de traiter une instance de n'importe quelle classe dérivée d'un ancêtre commun comme une instance de cet ancêtre commun – à l'aide de méthodes virtuelles – permet, lorsque joint aux templates, d'obtenir un modèle de programmation paramétrique et générique maximal en C++.

Ici encore, le standard offre une classe std::stack (bibliothèque <stack>), qui est de beaucoup supérieure à l'exemple académique proposé à droite (entre autres, std::stack est plus sécuritaire en présence d'exceptions; le code à droite, lui, ne l'est pas). Ne définissez vos propres conteneurs que quand un réel besoin existe, et assurez-vous d'être entouré(e) de professionnels expérimentés pour bien couvrir les considérations de sécurité, de vitesse, d'Exception-Safety, etc.

Cet exemple est déficient dans sa gestion des cas d'exceptions, mais nous éviterons la question dans cet article.

template<class T, int N=100>
   class Pile {
      T donnees[N];
      int nelems;
   public:
      Pile() : nelems{} {
      }
      int size() const {
         return nelems;
      }
      bool full() const {
         return size() == CAPACITE;
      }
      bool empty() const {
         return !size();
      }
      bool push(const T &elem) {
         bool succes = !empty();
         if (succes) {
            donnees[nelems] = elem;
            ++nelems;
         }
         return succes;
      }
      bool pop(T &elem) {
         bool succes = !empty();
         if (succes) {
            elem = donnees[nelems - 1];
            --nelems;
         }
         return succes;
      }
   };
int main() {
   Pile<float,50> PileFloat;
   Pile<char> Pilechar;
}

Pourquoi ne place-t-on habituellement pas la définition des templates dans un .cpp?

J'ai écrit ceci en réponse à une question de Fourat Djellouli, étudiant de la cohorte 10 du DDJV à l'Université de Sherbrooke, mais il s'agit d'une question récurrente. Pourquoi, en effet, ne place-t-on typiquement pas l'implémentation d'un template dans un fichier source, distinct du fichier d'en-tête qui en donne la déclaration?

Pour répondre à cette question, imaginons la situation suivante :

Fichier a.h
#ifndef A_H
#define A_H
template <class T>
   T f(T);
#endif
Fichier a.cpp
#include "a.h"
template <class T>
   T f(T x) {
      return x; // pass-through
   }
Fichier principal.cpp
#include "a.h"
int main() {
   int i = f(3);
}

Ici, a.cpp compilera sans peine : il ne contient pas de code, juste une recette pour que le compilateur génère du code sur demande. De même, principal.cpp compilera sans problème, car l'appel à f() respecte sa signature, au sens où le type de retour de la fonction correspond au type du paramètre qu'elle reçoit.

En C++, les .cpp sont compilés séparément. Cela signifie que a.cpp est compilé sans connaissance de principal.cpp, et que principal.cpp est compilé sans connaissance de a.cpp. Pour en savoir plus, voir ../Developpement/Programmation-Systeme--Mecanique-Compilation.html

Pour que l'édition des liens (qui joint les .obj générés à la compilation en un exécutable cohérent) fonctionne, il faut que l'appel à f() dans main() puisse être lié à une implémentation de f() pour laquelle T est int. Normalement, le compilateur aurait généré ce code pour nous en voyant que f(int) est appelé dans main(), mais pour cela, il faudrait qu'il ait en mains le code implémentant f() (sa définition, pas seulement sa déclaration).

En se limitant à un prototype de fonction dans a.h, le fichier que principal.cpp inclut, on ne donne pas assez d'information au compilateur pour qu'il puisse générer la définition associée à l'appel dans main(). Il faut comprendre que #include provoque une inclusion lexicale, sans plus. Ainsi, écrire ceci :

#include "a.h"
int main() {
   int i = f(3);
}

...est précisément équivalent à écrire cela :

#ifndef A_H
#define A_H
template <class T>
   T f(T);
#endif
int main() {
   int i = f(3);
}

Vous remarquerez que ce programme est incomplet : il ne permet pas au compilateur de savoir ce que fait f() (outre retourner un int si on lui passe un int en paramètre comme c'est le cas dans main() ici). Le compilateur, devant ces sources, sait que l'appel à f() est syntaxiquement et sémantiquement correct (donc ça compile), mais ne peut lier l'appel au code appelé (ce dernier n'ayant pu être généré).

Si nous insérons la définition du template dans a.h (et si nous supprimons a.cpp du portrait), nous avons maintenant ceci :

Fichier a.h
#ifndef A_H
#define A_H
template <class T>
   T f(T x) {
      return x; // pass-through
   }
#endif
Fichier principal.cpp
#include "a.h"
int main() {
   int i = f(3);
}

...et du point de vue du compilateur, une fois l'inclusion réalisée, nous avons :

#ifndef A_H
#define A_H
template <class T>
   T f(T x) {
      return x; // pass-through
   }
#endif
int main() {
   int i = f(3);
}

... ce qui donne au compilateur la capacité de générer le code pour l'appel f() dans main(), là où il est fait.

Passer un template en paramètre à un template

Il est possible de paramétrer un template à l'aide d'un template.

Supposons par exemple le code à droite, qui offre deux classes dont la signature générique est semblable, c'est-à-dire qui paramétrées sur la base d'un type (celui des éléments à y entreposer) et d'un entier (sa capacité), dans l'ordre.

Dans une optique de simplification, supposons aussi que les deux types offrent des services de même signature, mais avec une sémantique légèrement différente, au sens où :

  • Les méthodes push(), pop() et top() d'une Pile<T,N> implémentent une pile, donc une structure LIFO (Last In, First Out), alors que
  • Pour une File<T,N>, elles implémentent une file, donc une structure FIFO (First On, First Out)

Nous supposerons dans les deux cas un constructeur par défaut qui construit un objet vide.

template <class T, int N>
   class Pile {
      T elems[N];
      // ... push(), pop(), top(),
      // empty(), full(), etc.
   };
template <class T, int N>
   class File {
      T elems[N];
      // ... push(), pop(), top(),
      // empty(), full(), etc.
   }

Ensuite, supposons le code à droite qui est générique sur la base de C, qui est non pas un type mais un template sur la base d'un type et d'un entier, et d'un entier N. Ici, C est un template, pas un type, alors que C<string,3> est un type.

La fonction tester() instancie ensuite un C<float,N> dans lequel elle insère 0.5f, 1.5f, ..., (N-1)+0.5f dans l'ordre, puis affiche les éléments qu'elle en retire, un à la fois.

#include <ostream>
template <template <class, int> class C, int N>
   void tester(std::ostream &os) {
      C<float,N> conteneur;
      for (int i = 0; i < N; ++i)
         conteneur.push(0.5f + i);
      while (!conteneur.empty()) {
         os << conteneur.top() << std::endl;
         conteneur.pop();
      }
   }

Enfin, le programme de test utilise tester() sur une pile de dix éléments et sur une file de dix éléments. Notez la signature de l'appel ici, où les paramètres du template font partie de la fonction. Nous utilisons ici les mots Pile et File, qui ne sont pas des types mais bien des templates, et nous laissons le compilateur générer le code de la manière appropriée.

#include <iostream>
int main() {
   using std::cout;
   tester<Pile,10>(cout);
   tester<File,10>(cout);
}

Lectures complémentaires

Quelques liens pour enrichir le propos.

Outils

Le STLFilt, qui vise à clarifier et à épurer les messages d'erreurs générés lors de la compilation de code impliquant des templates. Notez que le développement actif de cet outil est chose du passé, puisque les auteurs, comme moi-même et bien d'autres, espèrent l'avènement des concepts pour C++ 17 : http://www.bdsoft.com/tools/stlfilt.html

Critiques

Selon Jacob Matthews, en 2003, les templates empêchent le compilateur de générer du code de qualité : http://www.kuro5hin.org/story/2003/5/26/22429/7674

Une discussion lancée par Scott Meyers en 2002 sur les risques de Code Bloat avec des templates : https://groups.google.com/forum/?hl=en#!topic/comp.lang.c++.moderated/KwBkmpNZl_U


[1] Tiré du dictionnaire universel francophone en ligne (Hachette) : Galvauder v. tr. Gâcher, avilir par un mauvais usage. Galvauder son génie, sa réputation.

[2] Notez qu'un template impliquant plusieurs types est tout à fait légal; ce n'est tout simplement pas le cas dans notre modèle simplifié.


Valid XHTML 1.0 Transitional

CSS Valide !