Les templates en C++

Septembre 2016


Introduction


Nous allons présenter la notion de template (patron en français). Les templates font parties des grands apports du C++ au langage C.

Jusqu'ici on passait en paramètre des fonctions des variables. Grâce au concept de template, il est possible de passer en paramètre des types et ainsi de définir des fonctions génériques. Mais le concept de template ne s'arrête pas aux fonctions, on peut aussi l'utiliser pour les classes et les structures.

Avantages


On appelle dans ce qui suit symbole indifféremment une fonction, une structure ou une classe. L'intérêt des templates réside dans sa :
- généricité : du moment que le type paramètre fournit tout ce qui est utilisé dans le symbole template, on peut passer n'importe quel type
- simplicité : on ne code qu'un symbole quel que soit le(s) type(s) passé(s) en paramètre, ce qui rend le code d'autant plus facile à maintenir

Inconvénients


- Comme nous allons le voir par la suite, l'utilisation de template requiert quelques précautions d'usage (typename...)
- Le programme est plus long à compiler.

Quand utiliser des templates ?


L'usage des templates est particulièrement pertinent pour définir des containers, c'est-à-dire des structures qui servent à stocker une collection d'objets (une liste, un vecteur, un graphe...). Voire aussi l'astuce sur le JDN : Comment afficher les nombres de 1 à 1000 en C ou C++ sans boucle ni structure conditionnelle ?)

Les templates sont également adaptés pour définir des algorithmes génériques s'appliquant à une famille de classe. Par exemple, il est intéressant de coder un algorithme de plus courts chemins indépendamment de la structure de graphe. On retiendra que l'usage de foncteurs peut s'avérer pertinent pour accéder aux poids installés sur les arcs du graphe dans ce cas-là. La classe de graphe passée en paramètre doit alors vérifier un certain nombre de prérequis pour que l'algorithme puisse être appliqué. Si ce n'est pas le cas le programme ne compilera pas...

Que dois-je mettre dans les .hpp et dans les .cpp ?


Le C++ étant un langage compilé, on ne peut évidemment pas imaginer de compiler pour un symbole donné toutes ses versions. Par exemple, si on définit une classe template de vecteur, que je vais noter my_vector<T>, on ne peut pas imaginer de compiler my_vector<int>, my_vector<char>, my_vector<my_struct> ... sachant qu'il y a une infinité de types pouvant être passés en paramètres.

C'est pourquoi une classe template est (re)compilée pour chaque type d'instance présent dans le programme. Ainsi, si dans mon programme j'utilise my_vector<int> et my_vector<char>, seules ces versions seront compilées. Si dans un autre programme j'utilise my_vector<my_vector<double> >, je compilerai juste my_vector<float> et my_vector<my_vector<float> >. Ce qu'il faut retenir, c'est que le compilateur se débrouille tout seul pour savoir quelles versions il doit compiler.

De tout ce qui vient d'être dit, on déduit qu'un symbole template ne peut être "précompilé", car il est compilé pour chaque instance. On retiendra donc la règle suivante :

Si un symbole template est utilisé uniquement dans un .cpp (fichier source), il peut être implémenté dans ce .cpp
Sinon, il doit être implémenté dans un .hpp (header).


Remarque :

Il peut arriver qu'un fichier contenant une classe template porte une extension différente des headers (.h ou .hpp), par exemple .tcc. Ceci n'est qu'une convention de notations. Personnellement, je les considère comme des headers à part entière.

Convention de notations


Les paramètres templates sont généralement notés avec une majuscule (tandis que les autres types sont généralement écrits en minucules). Dans la pratique, on fait comme on veut. Personnellement je les note précédés d'un T (par exemple Tgraph pour désigner un paramètre template représentant un graphe).

Ceci peut sembler anodin mais nous verrons que c'est assez pratique pour s'y retrouver avec les typenames et que ça rend le code plus lisible ;-)

Quelques templates célèbres

STL


La STL (Standard Template Library) est livrée de base avec les compilateurs C++. Cette librairie fournit un jeu de containers génériques, notamment :
std::vector : les vecteurs (tableau d'éléments de type T adjacents en mémoire), accès en O(1)
std::set : les ensembles d'éléments de type T sans doublon et ordonnés selon l'opérateur <, accès en O(log(n))
std::list : les listes chaînées (accès en O(n), insertion en début et fin de liste en O(1))

On pourra se faire une idée du contenu de la STL ICI

BGL


La BGL (Boost Graph Library) fournit des classes de graphe génériques et les algorithmes qui vont avec (algorithmes de plus court chemin, algorithme de flot, parcours de graphe, ...). On pourra se faire une idée du contenu de la BGL ICI

Celle-ci n'est pas présente par défaut mais s'installe facilement. Par exemple sous debian :
aptitude install libboost-graph-dev

Premiers pas


Pour manipuler des templates, on a besoin de quatre choses :

- le mot clé typename : il indique que le type qui suit est abstrait (paramètre template ou dépend d'un paramètre template) et qu'il ne doit être pris en compte qu'au moment où l'on instancie.

- le mot clé template : il indique que le symbole (structure, classe, fonction) qui va suivre prend des paramètres templates. On écrit directement après le mot clé template les paramètres templates (précédés du mot clé typename, struct, class, ou type de base selon le type de paramètre template attendu) entre chevrons, suivis du symbole écrit normalement. Attention à bien séparer les chevrons (fermants) afin qu'il ne soient pas confondus avec l'opérateur >> .

Dans cet exemple nous allons voir
- comment coder une classe template
- comment coder une fonction template
- comment coder un opérateur template
Dans cet exemple les symboles paramètres prennent juste un paramètre template, mais la démarche reste similaire avec plusieurs paramètres templates.

Exemple :
template <typename T1, typename T2, ... >
type_retour_t ma_fonction(param1_t p1,param2_t p2, ...){
...
}

template <typename T1, typename T2, ... >
class ma_classe_t{
...
};

template <typename T1, typename T2, ... >
struct ma_struct_t{
...
};


- l'opérateur :: : il permet d'accéder aux champs (en particulier les types) et les méthodes statiques d'une classe ou d'une structure. Il n'est pas spécifique aux templates (il s'applique aux classes et structures en général et aux namespaces). On peut le voir un peu comme le '/' des répertoires. Ainsi std::vector<int>::const_iterator signifie que j'accède au type const_iterator, stocké dans la classe vector<int>, elle-même codée dans le namespace std.

Nous allons définir notre propre classe de vecteur afin d'illustrer ce qui vient d'être dit. Évidemment en pratique on utilisera directement la classe std::vector de la STL...
#include <iostream>
//----------------------- début my_vector_t.hpp
#include <cstdlib>
#include <ostream>

// Une classe template prenant un paramètre
template <typename T>
class my_vector_t{
 protected:
  unsigned taille; // stocke la taille du vecteur
  T *data; // stocke les composantes du vecteur
 public:
  // Le constructeur
  my_vector_t(unsigned taille0 = 0,const T & x0 = T()):
   taille(taille0),
   data((T *)malloc(sizeof(T)*taille0))
  {
   for(unsigned i=0;i<taille;++i) data[i] = x0;
  }

  // Le destructeur
  ~my_vector_t(){
   free(data);
  }

  // Retourne la taille du vecteur
  inline unsigned size() const{
   return taille;
  }

  // Un accesseur en lecture seule sur la ième case du vecteur
  inline const T & operator[](unsigned i) const{
   if(i >= size()) throw;
   return data[i];
  }

  // Un accesseur en lecture écriture sur la ième case du vecteur
  inline T & operator[](unsigned i){
   if(i >= size()) throw;
   return data[i];
  }
};

// Un opérateur template
template <typename T>
std::ostream & operator<<(std::ostream & out,const my_vector_t<T> & v){
 unsigned n = v.size();
 out << "[ ";
 for(unsigned i=0;i<n;++i) out << v[i] << ' '; 
 out << ']'; 
 return out;
}

//----------------------- fin my_vector_t.hpp

// Une fonction template
template <typename T>
void ecrire(const my_vector_t<T> & v){
 unsigned n = v.size();
 std::cout << "[ ";
 for(unsigned i=0;i<n;++i) std::cout << v[i] << ' '; 
 std::cout << ']';
}

int main(){
 my_vector_t<int> v(5); // un vecteur de 5 entiers
 v[0] = 6; v[1] = 2; v[2] = 3; v[3] = 4; v[4] = 8;
 ecrire<int>(v); // appel de la fonction template
 std::cout << std::endl;
 ecrire(v); // appel implicite de ecrire<int>
 std::cout << std::endl;
 std::cout << v << std::endl; // appel de l'opérateur template
 return 0;
}

À l'exécution :
[ 6 2 3 4 8 ]
[ 6 2 3 4 8 ]
[ 6 2 3 4 8 ]

Tout ce qui est entre "début classe my_vector_t" et "fin classe my_vector_t" pourrait être déplacé dans un header (par exemple my_vector.hpp) puis être inclus par le programme principal.

Spécifications de templates


Rien n'empêche d'implémenter spécifiquement un symbole pour un jeu de paramètre template. Notons que rien n'oblige à spécifier tous les paramètres template. Dans ce cas le prototype le "moins template" est privilégié pour lever les ambiguïtés. Si on repart de l'exemple précédent :
#include "my_vector.hpp"

// Une spécification de template
void ecrire(const my_vector_t<int> & v){
    unsigned n = v.size();
    std::cout << "{ ";
    for(unsigned i=0;i<n;++i) std::cout << v[i] << ' ';
    std::cout << '}';
}

int main(){
    my_vector_t<int> v(5); // un vecteur de 5 entiers
    v[0] = 6; v[1] = 2; v[2] = 3; v[3] = 4; v[4] = 8;
    ecrire<int>(v); // appel de la fonction template
    std::cout << std::endl;
    ecrire(v); // appel à ecrire (prévaut sur l'appel implicite de ecrire<int>)
    std::cout << std::endl;
    std::cout << v << std::endl; // appel de l'opérateur template
    return 0;
}

À l'exécution :
[ 6 2 3 4 8 ]
{ 6 2 3 4 8 }
[ 6 2 3 4 8 ]

Template par défaut


Il est également possible de préciser un paramètre template par défaut de la même façon que pour un paramètre de fonction.

Par exemple :
template<typename T = int>
class my_vector_t{
   //...
};

int main(){
  my_vector<> v; // un vecteur d'int
  return 0;
}

Quelques exemples célèbres de templates par défaut : dans la STL le foncteur de comparaison, utilisé dans les std::set, est initialisé par défaut par std::less (foncteur de comparaison basé sur <). Ainsi on peut écrire indifféremment :
std::set<int> s;
std::set<int,std::less<int> > s_;

Récupérer des paramètres templates, des types et des méthodes statiques d'une classe template


Une bonne affaire avec les classes templates, c'est de mettre des typedef (en public) pour pouvoir récupérer facilement les paramètres templates. Exemple : j'ai une classe c1<T> et je veux récupérer le type T. Ceci va être possible grâce à typedef et typename.
template <typename T>
struct my_class_t{
 typedef T data_t;
};

int main(){
 typedef my_vector_t<int>::data_t data_t; // Ceci est un entier
}

Cependant on ne peut appliquer l'opérateur :: que si un membre de gauche n'est pas un type abstrait (ie dépendant d'un type template pas encore évalué). Par exemple, si je veux manipuler le typedef "const_iterator" de la classe std::vector fournie par la STL, si les paramètres templates de std::vector ne sont pas affectés le programme refusera de compiler :
void ecrire(const std::vector<int> & v){
 std::vector<int>::const_iterator vit(v.begin(),vend(v.end());
 for(;vit!=vend;++vit) std::cout << *vit << ' ';
}

template <typename T>
void ecrire(const std::vector<int> & v){
 std::vector<T>::const_iterator vit(v.begin(),vend(v.end()); // ERREUR !
 for(;vit!=vend;++vit) std::cout << *vit << ' ';
}

Ici le std::vector<T> est situé à gauche d'un :: et dépend d'un paramètre template. C'est la que typename entre en jeu.
template <typename T>
void ecrire(const std::vector<int> & v){
 typename std::vector<T>::const_iterator vit(v.begin(),vend(v.end());
 for(;vit!=vend;++vit) std::cout << *vit << ' ';
}

On retiendra que quand le type à gauche d'un :: dépend d'un paramètre template, il doit être précédé d'un typename. Etant donné que les types deviennent rapidement lourds à manipuler, il est judicieux de faire des typedef. Sur un autre exemple, plus compliqué, ça donne par exemple:
typedef typename std::vector<typename std::vector<T>::const_iterator>::const_iterator mon_type_bizarre_t

Templates récursifs


Il est possible de définir des templates récursifs (si si !). Un exemple :
#include <iostream>

template <int N>
int fact(){
 return N*fact<N-1>();
}

template <>
int fact<0>(){
 return 1;
}

int main(){
 std::cout << fact<5>() << std::endl;
 return 0;
}

Ici l'intérêt est assez modéré car concrètement on compile fact<5>, fact<4>... fact<0>, c'est vraiment juste pour donner un exemple simple de template récursif.

Quel intérêt d'un template récursif du coup ? Eh bien dans boost, le template récursif permet d'implémenter des tuples génériques ! Pour les petits curieux ça se tient dans /usr/include/boost/tuple/detail/tuple_basic.hpp, donc je ne m'étendrai pas davantage ;-)

Tester des valeurs de type template


Il est possible avec boost de vérifier si un type template correspond à un type attendu et de bloquer la compilation le cas échéant. Étant donné que ça utilise la librairie boost, je donne juste un bref exemple :
#include <boost/type_traits/is_same.hpp>
#include <boost/static_assert.hpp>

template <typename T>
struct ma_struct_qui_ne_doit_compiler_que_si_T_est_int{
 BOOST_STATIC_ASSERT((boost::is_same<T,int>::value));
 //...
};

Liens utiles


Cours sur le C++, la partie sur les templates est très bien expliquée et très détaillée :
http://www.nawouak.net/?doc=course.cpp+ch=templates+lang=fr

Présentation de la STL (Standard Template Library) : elle propose de nombreux containers templates) :
http://www.sgi.com/tech/stl/
http://www.commentcamarche.net/faq/sujet 11255 introduction a la stl en c standard template library

Présentation de la BGL (Boost Graph Library) : une sous-partie de la librairie boost, elle propose des classes et des algorithmes de graphes templates) :
http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/table_of_contents.html

A voir également :

Ce document intitulé «  Les templates en C++  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.