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...).
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
Lire la suite
Les inlines en C++ »
Publié par
mamiemando -
Dernière mise à jour le 13 novembre 2009 à 13:15 par marlalapocket
* Le polymorphisme est l'une des pierres angulaires du paradigme objet
