Programmation générique et templates

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.

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.

int a = 3, b = 5, c;
c = min(a, b);

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...

int main() {
   int i1 = 3, i2 = 5, i3;
   float f1 = 12.5f, f2 = -27.3f, f3;
   i3 = min (i1, i2);
   f3 = min (f1, f2);
}

...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 = (((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 modifie 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.

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

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

• Sera capable d'opérer peu importe les types impliqués, dans la mesure où les contraintes du template en question sont respectées
• Ne demandera pas d'écrire le code de fonctions pour chaque combinaison de type
• N'impliquera pas plus de charge administrative (overhead) à l'exécution que ne le ferait une fonction aux types non paramétriques

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 mot clé template signifie que ce qui suit sera un template au sens C++, c'est-à-dire une unité de code faisant appel à des types paramétriques
• L'écriture <class T> signifie que T, tel qu'utilisé dans cette unité de code, sera un type paramétrique. Notez que le mot class signifie ici que le type est paramétrique, et non pas qu'il s'agit d'une classe; notre min() fonctionnera très bien avec des int et des float
• Ainsi, partout dans l'unité de code où on retrouvera le symbole T, on pourra remplacer T par n'importe quel type, dans la mesure où il s'agit du même type dans tous les cas pour une seule et même utilisation
• Le T qui précède le mot min signifie que la fonction retournera une valeur du type signifié par T
• Le T qui précède a et b est porteur du même sens: il indique qu'il s'agit dans chaque cas du même type, peu importe lequel. Ceci s'applique aussi au T précédant le symbole resultat, qui sert à déclarer Resultat comme étant du même type que a, b et la fonction elle-même

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

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 à :

• La possibilité de générer une copie d'une instance du type
• La capacité de créer une instance par défaut du type
• La capacité de comparer deux instances du type à l'aide de l'opérateur <
• La capacité d'affecter une instance du type à une autre
• La capacité d'invoquer une méthode portant un nom précis, etc.

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.

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

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

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

// 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

template<class T, int N>
   class Tampon {
      T donnees[N] {};
      static const int taille = N;
   public:
      Tampon() = default;
      // ...
   };

#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

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;
   }

template<class T, int N=100>
   class Pile {
      T donnees[N];
      int nelems {};
   public:
      Pile() = default;
      int size() const noexcept {
         return nelems;
      }
      bool full() const noexcept {
         return size() == N;
      }
      bool empty() const noexcept {
         return !size();
      }
      bool push(const T &elem) {
         bool succes = !full();
         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 :

#ifndef A_H
#define A_H
template <class T>
   T f(T);
#endif

#include "a.h"
template <class T>
   T f(T x) {
      return x; // sorte de « pass-through »
   }

#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.

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 :

#ifndef A_H
#define A_H
template <class T>
   T f(T x) {
      return x; // sorte de « pass-through »
   }
#endif

#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; // sorte de « 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.

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.
   }

#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();
      }
   }

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

Lectures complémentaires

Quelques liens pour enrichir le propos.

• Questionnement de Bjarne Stroustrup en 1993 sur les principaux écueils qu'il perçoit avec l'avènement des templates : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1993/N0288.pdf
• Plaidoyer de Bjarne Stroustrup en 1996 pour le maintien de la compilation séparée des fichiers sources, même avec l'avènement des templates : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1996/N0885.pdf
• En 1997, Bjarne Stroustrup explique ce qu'il estime être des problèmes avec les paramètres de templates munis de valeurs par défaut : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1070.pdf
• Des alias pour des templates, par Bjarne Stroustrup en 2003 : http://www.stroustrup.com/template-aliases.pdf
• Fonctions génériques :
  • pourquoi, avec C++ 98, ne spécialise-t-on pas une fonction template? Texte par Herb Sutter en 2001 : http://www.gotw.ca/publications/mill17.htm
  • texte explicatif par Danny Kalev en 2003 : hhttp://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=51
• Comment g++ instancie un template : https://gcc.gnu.org/onlinedocs/gcc/Template-Instantiation.html
• Discussion des templates extern, maintenant supprimés du langage, par John Spicer en 2006 : http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2006/n1987.htm
• Utiliser les templates pour implémenter des fonctions de rappel (des Callbacks), par Arash Partow en 2008 : http://partow.net/programming/templatecallback/index.html
• Texte de 2015 expliquant comment spécialiser explicitement un membre non-générique d'une classe générique : http://arkfps.github.io/2015/01/12/providing-explicit-specializations-for-non-template-members-of-class-template
• Passer une fonction surchargée en paramètre à un template, un tour de passe-passe proposé par Florian Weber en 2015 : http://florianjw.de/en/passing_overloaded_functions.html
• En quoi les templates permettent une forme de Duck Typing, par Andrew Koenig et Barbara Moo en 2005 : http://www.drdobbs.com/templates-and-duck-typing/184401971
• Texte de 2010 expliquant comment améliorer les messages d'erreurs obtenus en compilant des templates : http://cpp-next.com/archive/2010/09/expressive-c-why-template-errors-suck-and-what-you-can-do-about-it/
• Transformer du code générique en « bon citoyen » d'un programme, par Victor Laskin en 2015 : http://vitiy.info/templates-as-first-class-citizens-in-cpp11/
• Texte de 2015 qui nous rappelle qu'il ne faut pas avoir peur des templates : http://cpp.indi.frih.net/blog/2015/04/code-critique-fear-of-templates-makes-power-set-implementation-useless/
• En 2017, Gordon Brown explique le recours aux mots typename et template dans un programme : http://www.aerialmantis.co.uk/blog/2017/03/17/template-keywords
• Les ajustements aux templates avec C++ 17, texte de Bartlomiej Filipek en 2017 : http://www.bfilipek.com/2017/06/cpp17-details-templates.html
• Une introduction aux templates, proposée par Paul M. Watt en 2017 : http://codeofthedamned.com/index.php/fundamentals-of-c-templates

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é.