Nous allons présenter la notion de template (patron en français). Les templates font parties des grands apports du C++ par rapport au langage C.
Ils permettent de paramétrer un type ou une fonction par un (ou plusieurs) type(s). Par exemple, en C, si on veut définir un vecteur de flottants et une liste d'entiers, on est contraint de définir deux structures dédiées. En C++, on peut abstraire le type encapsulé par le vecteur si la classe implémentant le vecteur est "template".
On appelle dans ce qui suit symbole indifféremment une fonction, une structure ou une classe.
Avantages
Du moment que le(s) type(s) passé(s) en paramètre sont adaptés, on peut passer n'importe quel type à la classe template. Ainsi 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
Les templates requierent quelques précautions d'usage (typename...)
Le programme est plus long à compiler.
L'implémentation d'une classe / structure / fonction template doit être faite dans un header (fichier
.hpp
) afin d'être réutilisable. Pour rappel, on n'inclue jamais un fichier source (fichier
.cpp
) depuis un autre fichier afin d'éviter des erreurs en fin de compilation (linkage). Il est important de comprendre que c'est parfaitement normal pour un template : le compilateur ne sait pas à l'avance quelles déclinaisons du symbole template il va devoir compiler, il faut donc que cette définition soit connue par l'ensemble des fichiers sources qui en auront besoin. En effet, contrairement aux symboles non template, il n'y a pas une manière absolue de compiler le symbole template (dans un fichier
.o
).
Quand utiliser des templates ?
Pour une classe stockant une collection d'objets arbitraire (une liste, un vecteur, un graphe...).
Pour implémenter un algorithme devant s'abstraire partiellement de la structure de données passée en paramètre. Par exemple, la librairie boost implémente l'algorithme de Dijkstra de sorte à s'abstraire de la structure du graphe (du moment qu'elle hérite d'une structure de graphe boost adaptée), des primitives de calcul (comparaison et concaténation pour le calcul des meilleurs chemins), et des structures stockant les résultats du calcul.
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 :
: les listes chaînées (accès en O(n), insertion en début et fin de liste en O(1)).
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, ...).
La BGL s'installe facilement sous Linux. Par exemple, sous Debian et les distributions qui en dérivent :
sudo apt install libboost-graph-dev
Pré-requis
Pour rappel, le C++ introduit (comparé au C) aussi l'opérateur ::. Il permet d'accéder aux déclarations (types, méthodes, ...) faites dans une classe / structure ou dans un espace de nommage. On peut le voir un peu comme le '/' des répertoires. Il n'est pas donc spécifique aux templates, mais souvent utilisé dans ce contexte. Par exemple, le type
std::vector<int>::const_iterator
signifie que l'on récupère le type
const_iterator
, stocké dans la classe
vector<int>
, elle-même codée dans le
namespace std
.
Par ailleurs, le C++ introduit deux mots clés pour gérer les classes templates :
Pour la déclaration, 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 >> .
Pour l'utilisation, le mot clé
typename
: il indique que le type qui suit n'est pas encore résolu car il dépend encore d'un ou plusieurs paramètres template. Il n'est donc utile que lorsqu'on déclare un symbole template, en vue de déclarer quelque chose d'autre.
Exemple 1 : pas de
typename
:
void f(const std::vector<int> & v) {
std::vector<int>::const_iterator it = v.begin(); // Ne dépend pas d'un type template
}
Exemple 2 :
typename
nécessaire :
template <typename T>
void f(const std::vector<T> & v) {
typename std::vector<T>::const_iterator it = v.begin(); // Type template à gauche d'un :: => besoin de typename
}
Convention de notations
Les paramètres templates sont généralement notés en camel case (par exemple
MonType
) alors que les autres types sont notés en minuscules et suffixés par
_t
(par exemple
mon_type_t
). Si on préfère utiliser tout le temps le style camel case, il est recommandé de préfixer les paramètres templates par
T
(par exemple
TMonType
)
Suivre cs conventions n'est pas obligatoire, mais aide à savoir quand le mot clé
Lorsqu'on déclare une instance dépendant d'une structure / classe template, les paramètres templates (non optionnels) doivent être explicités.
Lorsqu'on appelle une fonction ou une méthode template, si les paramètres de celles-ci permettent de déduire ses paramètres template, on peut les omettre. Sinon il faut les préciser.
Exemple détaillé
L'exemple ci-dessous montre comment implémenter une classe de vecteur plus simple que
std::vector
:
my_vector.hpp
#include <iostream>
#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;
}
main .cpp
#include "my_vector.hpp"
// Une fonction template (comme on ne l'utilise que dans ce fichier, pas besoin de la mettre dans un fichier header)
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;
}
Résultat :
[ 6 2 3 4 8 ] [ 6 2 3 4 8 ] [ 6 2 3 4 8 ]
Utilisations avancées
Spécifications de templates
Rien n'empêche d'implémenter spécifiquement un symbole pour un jeu de paramètres templates. Rien n'oblige à spécifier des paramètres template qui peuvent être déduits automatiquement par le compilateur. En cas d'ambiguïté, le compilateur privilégie la déclaration la "moins template".
Ici, on modifie
ecrire
pour que celle-ci ne soit spécifiquement utilisable que pour des
vector<int>
:
#include "my_vector.hpp"
// Une fonction template (comme on ne l'utilise que dans ce fichier, pas besoin de la mettre dans un fichier header)
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 << ']';
}
// Spécification de template (on pourrait garder sans problème l'ancienne déclaration en plus)
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;
}
Résultat :
{ 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 :
Récupérer des paramètres templates, des types et des méthodes statiques d'une classe template
Il est recommandé d'exposer à l'aide de
typedef
publics les types templates paramétrant la classe qu'on implémente. Cela permet depuis les classes qui utilise notre classe de récupérer les paramètres templates qui ont été utilisés.
Exemple :
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
}
Templates récursifs
Il est possible de définir des templates récursifs.
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;
}
Concrètement, ce code va engendrer la compilation de
fact<5>
,
fact<4>
...
fact<0>
. Cet exemple jouet n'a pas d'intérêt pratique, mais montre que c'est possible. Une cas de template récursif plus intéressant (mais plus compliqué) est celui mis en œuvre dans la librairie boost pour implémenter les tuples génériques.
Tester des valeurs de type template (avec boost)
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 :
