Les templates variadiques en C++
Voir aussi : code source - vidéo youtube - vidéo peertube
Les templates variadiques sont des templates qui peuvent recevoir un nombre variable de paramètres. On peut donc les voir comme l’équivalent des fonctions variadiques (comme la fonction printf
) mais pour les templates. Ils permettent d’implémenter des structures de données complexes, comme par exemple des tuples, tout en profitant du système de typage du compilateur. Les templates variadiques utilisent généralement des fonctionnalités classiques en programmation fonctionnelle, comme la récursivité ou la réduction.
Compléments sur les templates
Les paramètres non-types
Les templates sont souvent utilisés pour écrire du code générique par rapport à un type. Par exemple, on peut ainsi écrire un template pour définir une fonction sur un int
ou sur un double
ou autre. Autre exemple, le template de classe vector
permet de créer des tableaux de int
ou de double
ou autre.
<int> v1; // v1 est un tableau d'entiers, de taille dynamique vector
Cependant, les templates peuvent également prendre des paramètres “non-types”, c’est-à-dire des paramètres qui ne représentent pas un type générique mais une valeur (d’un type prédéfini). Par exemple, le template de classe array
prend en paramètre le type des éléments du tableau mais également le nombre d’éléments du tableau, c’est-à-dire un int
.
<int, 3> v2; // v2 est un tableau de 3 entiers array
Par exemple, la structure Constant
suivante permet de représenter un entier non modifiable.
struct Constant {
const int _value; // valeur de l'entier
(int value) : _value(value) {}
Constantint getValue() const { return _value; } // accès à la valeur de l'entier
};
int main() {
(1);
Constant c1<< c1.getValue() << endl;
cout
(2);
Constant c2<< c2.getValue() << endl;
cout
return 0;
}
On peut également implémenter Constant
par un template dont le paramètre est la valeur de l’entier à représenter. On peut même oublier complètement l’attribut _value
car sa valeur est déjà connue, avec le paramètre du template.
template <int V>
struct Constant {
() = default;
Constantint getValue() const { return V; } // ici la valeur de l'entier est connu
// d'après le paramètre du template
};
int main() {
<1> c1;
Constant<< c1.getValue() << endl;
cout
<2> c2;
Constant<< c2.getValue() << endl;
cout
return 0;
}
Run-time vs compile-time
Un des points essentiels des templates est qu’ils sont instanciés à la compilation (compile-time) et non à l’exécution (run-time). Ceci permet au compilateur de vérifier le typage et d’optimiser le code généré. En revanche,
les paramètres du template doivent être connus dès la compilation.
Par exemple avec la structure Constant
précédente, la version template n’est utilisable que si on connait la valeur représentée dès la compilation. Si cette valeur est connue à l’exécution, par exemple lors d’une saisie clavier ou via les arguments de la ligne de commande, alors la version template n’est pas applicable et il faut utiliser la version run-time classique.
Les templates récursifs
Les templates peuvent réaliser de la récursivité. Prenons l’exemple très classique de la suite de Fibonacci. Avec une implémentation (naïve et inefficace) sous forme de fonction récursive, on aurait le code suivant.
int fibo(int n) {
assert(n >= 0);
return n <= 1 ? n : fibo(n-1) + fibo(n-2); // fonction récursive naïve
}
int main() {
<< fibo(0) << endl;
cout << fibo(1) << endl;
cout << fibo(2) << endl;
cout << fibo(3) << endl;
cout << fibo(42) << endl;
cout return 0;
}
On peut implémenter un code équivalent avec des templates. Pour cela, on définit un template de structure paramétré par un int
(la position dans la suite de Fibonacci) et contenant un attribut value
(la valeur dans la suite pour cette position). L’attribut est calculé à l’instanciation du template, en instanciant récursivement le même template mais pour une valeur de paramètre différente. Comme pour toute définition récursive, il faut, en plus des appels récursifs, définir les cas terminaux. Ici, on pré-instancie le template pour les valeurs 0 et 1 de son paramètre.
template <int N> struct Fibo {
static const int value = Fibo<N-1>::value + Fibo<N-2>::value;
// instanciations récursives du template
};
template<> struct Fibo<0> {
static const int value = 0;
// instance terminale pour le paramètre de valeur 0
};
template<> struct Fibo<1> {
static const int value = 1;
// instance terminale pour le paramètre de valeur 1
};
int main() {
<< Fibo<0>::value << endl;
cout << Fibo<1>::value << endl;
cout << Fibo<2>::value << endl;
cout << Fibo<3>::value << endl;
cout << Fibo<42>::value << endl;
cout return 0;
}
Bien entendu, cette implémentation de la suite de Fibonacci n’est utilisable que pour des valeurs du paramètre connues à la compilation.
On remarquera cependant que :
- la suite est calculée à la compilation, donc l’exécution est très rapide (simple accès à l’attribut
value
); - les templates ne sont instanciés que si nécessaire; ce qui veut dire qu’il n’y a pas de recalcul des valeurs déjà calculées (memoïzation) et donc que malgré l’écriture naïve des appels récursifs, le calcul est réalisé efficacement.
Templates variadiques, exemple 1 (Adder)
On veut implémenter une structure Adder
. Cette structure est initialisée en lui passant un tableau d’entiers, dont elle calcule et stocke la somme.
Version run-time
Dans une version classique “run-time”, on utiliserait une structure avec un attribut _result
. Le tableau d’entier serait passé en paramètre du constructeur, qui calculerait la somme et la stockerait dans _result
.
struct Adder {
int _result;
(const vector<int> & values) {
Adder= accumulate(values.begin(), values.end(), 0, plus<int>());
_result // le résultat est calculé lors de la construction de l'objet
}
};
int main() {
({1});
Adder a1<< a1._result << endl;
cout ({1,2,3});
Adder a3<< a3._result << endl;
cout return 0;
}
Version templates variadiques, par recursion
Dans une version “compile-time”, on peut passer les entiers comme paramètres de template. Il suffit donc de définir un template de structure variadique. Cette structure contient un attribut _result
qui est calculé récursivement en ajoutant à la valeur du premier paramètre l’attribut _result
du template correspondant au reste des paramètres.
template<int ... XS> struct Adder;
template<int X>
struct Adder<X> {
static const int _result = X;
// instance terminale : s'il n'y a qu'un paramètre,
// alors le résultat est la valeur de ce paramètre
};
template<int X, int ... XS>
struct Adder<X, XS ...> {
static const int _result = X + Adder<XS...>::_result;
// instanciation récursive : le résultat est la somme
// du premier paramètre et du résultat de l'instanciation sur
// le reste des paramètres
};
int main() {
<1> a1;
Adder<< a1._result << endl;
cout <1,2,3> a3;
Adder<< a3._result << endl;
cout << Adder<1,2,3>::_result << endl;
cout return 0;
}
On notera que le paramètre variadique est noté sous la forme int ... XS
. Le symbole ...
est parfois appelé “ellipse”.
Version templates variadiques, par folding
Depuis la norme C++17, on peut utiliser des “fold expressions”, c’est-à-dire des calculs de réduction sur le paramètre variadique. Ceci permet généralement de simplifier signicativement le code.
template <int ... XS>
struct Adder {
static const int _result = (0 + ... + XS); // utilisation d'une "fold expr"
};
int main() {
<1> a1;
Adder<< a1._result << endl;
cout <1,2,3> a3;
Adder<< a3._result << endl;
cout << Adder<1,2,3>::_result << endl;
cout return 0;
}
On notera que tous les codes ne sont pas forcément implémentables sous forme de fold expressions et qu’il est donc parfois nécessaire d’utiliser une forme récursive.
Templates variadiques, exemple 2 (Tensor)
L’exemple précédent est très artificiel. L’exemple ci-dessous illustre une utilisation plus réaliste des templates variadiques. Il s’agit de définir des tableaux multi-dimensionnels de tailles statiques avec quelques fonctionnalités de base : remplir le tableau avec une valeur donnée, accéder à un élément dans le tableau, ajouter un tableau dans un autre, multiplier toutes les valeurs par une constantes… Les templates permettent ici de réaliser certains calculs et vérifications dès la compilation et donc d’optimiser l’exécution.
Version run-time
struct Tensor {
<int> _dims;
vector<double> _data;
vector
explicit Tensor(const vector<int> & dims) : _dims(dims) {
int n = accumulate(_dims.begin(), _dims.end(), 1, multiplies<int>());
.resize(n);
_data}
void fill(const double & v) {
std::fill(_data.begin(), _data.end(), v);
}
int ind(const vector<int> & inds) const {
assert(inds.size() == _dims.size());
assert(inds[0]<_dims[0]);
int k = inds[0];
for (unsigned i=1; i<_dims.size(); i++) {
assert(inds[i]<_dims[i]);
= k * _dims[i] + inds[i];
k }
return k;
}
double & operator()(const vector<int> & is) {
return _data[ind(is)];
}
const Tensor & operator+=(const Tensor & t) {
assert(_data.size() == t._data.size());
for (unsigned i=0; i<t._data.size(); i++)
[i] += t._data[i];
_datareturn *this;
}
};
operator*(double k, const Tensor & t1) {
Tensor (t1._dims);
Tensor t2for (unsigned i=0; i<t1._data.size(); i++)
._data[i] = k * t1._data[i];
t2return t2;
}
#include <iostream>
int main() {
({2,3,4});
Tensor t1.fill(7.0);
t1({2,3,4});
Tensor t2.fill(3.0);
t2= 2.0 * t1;
Tensor t3
+= t2;
t1 << t1({1, 2, 3}) << endl;
cout << t2({1, 2, 3}) << endl;
cout << t3({1, 2, 3}) << endl;
cout
({1, 2, 3}) = 0.0;
t1<< t1({1, 2, 3}) << endl;
cout
({2});
Tensor t4.fill(22.0);
t4({2});
Tensor t5.fill(20.0);
t5+= t5;
t4 = 2.0 * t4;
Tensor t6 << t6({1}) << endl;
cout
+= t4; // erreur détectée à l'exécution
t1
return 0;
}
Version template variadique
template <int ... XS>
struct Tensor {
static const int _K = (1 * ... * XS);
<double, _K> _data;
arraystatic const int _D = sizeof...(XS);
static constexpr array<int, _D> _dims {XS...};
static_assert(_D > 0);
void fill(const double & v) {
.fill(v);
_data}
int ind(const array<int, _D> & inds) const {
assert(inds[0]<_dims[0]);
int k = inds[0];
for (int i=1; i<_D; i++) {
assert(inds[i]<_dims[i]);
= k*_dims[i] + inds[i];
k }
return k;
}
double & operator()(const array<int, _D> & inds) {
return _data[ind(inds)];
}
const Tensor<XS...> & operator+=(const Tensor<XS...> & t) {
(_data.begin(), _data.end(), t._data.begin(),
transform.begin(), plus<double>());
_datareturn *this;
}
};
template <int ... XS>
const Tensor<XS...> operator*(double k, const Tensor<XS...> & t1) {
<XS...> t2;
Tensorfor (int i=0; i<t1._K; i++)
._data[i] = k * t1._data[i];
t2return t2;
}
#include <iostream>
int main() {
<2,3,4> t1;
Tensor.fill(7.0);
t1<2,3,4> t2;
Tensor.fill(3.0);
t2<2,3,4> t3 = 2.0 * t1;
Tensor
+= t2;
t1 << t1({1,2}) << endl;
cout << t2({1,2,3}) << endl;
cout << t3({1,2,3}) << endl;
cout
({1,2,3}) = 0.0;
t1<< t1({1,2,3}) << endl;
cout
<2> t4;
Tensor.fill(22.0);
t4<2> t5;
Tensor.fill(20.0);
t5+= t5;
t4 <2> t6 = 2.0 * t4;
Tensor<< t6({1}) << endl;
cout
+= t4; // erreur détectée à la compilation
t1
return 0;
}
Conclusion
Les templates C++ proposent des fonctionnalités assez avancées. Ils permettent d’implémenter des structures avec des paramètres arbitraires mais correctement typés comme les tuples ou des bibliothèques de meta-programmation évoluées comme Boost Hana.
Les templates sont un aspect assez avancé du C++, qu’il peut être utile de maitriser pour développer des bibliothèques évoluées. Mais pour de nombreux cas d’utilisation du C++, une connaissance beaucoup plus basique est généralement largement suffisante.