Title: Jouons avec C++11: métaprogrammation et variadic templates Date: 2013-05-19 12:26:00 Tags: c++, c++11, templates, variadic templates, metaprogrammation Author: Mathieu Stefani
Aujourd'hui nous allons nous détendre avec un peu de C++, mais pas n'importe quel C++ ! Nous allons faire du C++11 et nous allons explorer ensemble une fonctionnalité très intéressante et aux nombreuses possibilités du langage : les variadic templates.
Pour donner un avant-goût aux plus impatiants, au travers de cet article, nous allons nous amuser avec notre compilateur afin de lui faire faire réaliser un ensemble d'opérations pendant même la phase de compilation. En C++, c'est ce qui constitue la propriété unique des templates: ils sont évalués à la compilation et non pas à l'exécution.
Mais avant de nous lancer tête baissée dans le sujet, il est dans un premier temps nécessaire de replacer un peu de contexte sur C++11 ainsi que les templates avant d'attaquer la partie amusante.
Rassurez-vous, C++ n'en est pas à sa version 11, mais plutôt à sa troisième version. Petit cours d'histoire pour les retardataires :
C++ est un langage qui est normalisé et qui dispose donc d'un document complet de spécification. Bien que les travaux sur celui-ci aient commencés en 1979 par Bjarne Stroustrup, son créateur, la première normalisation du C++ a eu lieu en 1998, détenue par l'organisme international ISO. À cette époque, cette norme a donné lieu au C++98, pour 1998. S'en est suivi en 2003 un « Technical Corrigendum » consistant en des corrections mineures du précédent document, qui a donné naissance au C++98/03, aussi désigné C++03.
Depuis 2003, aucune nouvelle norme n'a donc été publiée jusqu'en Octobre 2011. L'année 2011 a marqué un tournant majeur dans le monde et la communauté du C++ car elle a donné lieu à une « renaissance » du langage C++ en formant C++11. Cette nouvelle norme a apporté un lot important de nouvelles fonctionnalités au langage parmis lesquelles 1 :
- Les fonctions anonymes (lambda expressions) ;
- Les boucles de type foreach (for-range based loops) ;
- L'inférence de type avec le mot-clé auto ;
- L'apparition de la notion de multi-threading dans la bibliothèque standard ;
- ...
- Les variadic templates.
Tout au long de cet article, c'est donc les variadic templates qui vont tout particulièrement nous intéresser. Mais avant toute chose, commençons par rappeler à quoi correspondent les templates en C++.
en C++, les templates définissent le modèle de généricité du langage. En effet, l'un des enjeux majeurs lorsqu'on écrit du code est de concevoir son architecture de sorte qu'elle soit le plus générique possible, c'est à dire que son fonctionnement soit identique quel que soit les types de données sur lesquels elle agit. C'est ce que l'on appelle la généricité et c'est le problème qu'adressent en premier les templates du C++.
Les templates permettent de définir des modèles de classes ou de fonctions
dont le comportement est identique pour un ensemble fini ou infini de types de
données.
Un bon exemple serait une fonction max 2 permettant de retourner le maximum
de deux éléments passés en paramètre. Pour des entiers, on aurait donc la fonction
suivante:
:::cpp
int max(int a, int b) {
return a > b ? a : b;
}
Mais cette fonction pourrait tout aussi bien fonctionner sur des éléments à virgule flottante de type double:
:::cpp
double max(double a, double b) {
return a > b ? a : b;
}
On se rend donc très rapidement compte qu'une telle fonction fonctionne pour
n'importe quel type pouvant être comparé à l'opérateur >.
Grace aux templates, on peut définir le modèle de fonction suivant :
:::cpp
template<typename T>
T max(const T &a, const T &b) {
return a > b ? a : b;
}
max est ici un modèle de fonction générique fonctionnant pour n'importe
quel type T pouvant être comparé avec l'opérateur >. Ce modèle va ensuite
servir au compilateur qui s'occupera automatiquement de générer le code
spécifique à chaque type. On parle alors d'instanciation. Par exemple, pour
deux éléments de type int, le compilateur va générer le code suivant :
:::cpp
int max(const int &a, const int &b) {
return a > b ? a : b;
}
Le compilateur a donc tout simplement remplacé le type générique de base T par le type int.
Tout comme avec les fonctions, l'une des grandes forces des templates C++ consiste
à pouvoir écrire des modèles de classes. Dans la bibliothèque standard du C++,
un très grand nombre de classes utilisent ce principe et sont en réalité des
classes template comme par exemple std::vector qui est un conteneur permettant
de stoquer un ensemble indéterminé d'éléments de façon contigue en mémoire.
vector peut-être utilisé avec n'importe quel type pouvant être copié 3:
:::cpp
std::vector<std::string> content;
content.push_back("Line 1");
content.push_back("Line 2");
On dit que l'expression std::vector<std::string> instancie un objet vector
avec le type std::string.
La syntaxe permettant de déclarer une classe template est rigoureusement la même que pour une fonction template:
:::cpp
template<typename T, size_t N = 100>
class FixedBuffer {
private:
T buffer_[N];
};
Avec ce modèle de classe template, l'expression FixedBuffer<int> buf génèrera
le code spécifique pour le type int. Dans cette déclaration, on peut également
remarquer un autre paramètre qui n'est pour sa part pas générique puisqu'il
s'agit d'un simple paramètre template de type size_t 4. Cela s'appelle un
paramètre template non-typé (non-type template parameter) et permet de spécifier
des valeurs constantes à la compilation. Ici le paramètre template non-typé N
a une valeur par défaut de 100 mais peut-être modifié à la compilation :
:::cpp
FixedBuffer<int, 255> buf; /* buffer fixe de 255 int */
Cependant, un ensemble de restrictions s'appliquent quant à ce genre de paramètre
template. Pas tous les types ne peuvent-être utilisés. Il est par exemple illégal
de déclarer un paramètre template non-typé std::string :
:::cpp
template<std::string S> class Wrapper { // Illégal, S ne peut pas être std::string
};
Comme nous venons de le démontrer, les templates constituent une part importante du langage C++. Cependant, outre l'aspect premier de généricité, les templates, de part leur nature, offrent des possibilités de métaprogrammation que nous allons nous empresser de découvrir.
Après leur conception, il a été découvert par hasard que les templates étaient en réalité turing-complet signifiant que toute logique pouvait être exprimée et formalisée grace aux templates.
Grace aux templates, des problèmes initialement résolus à l'exécution peuvent
donc être désormais résolus directement à la compilation. Cela peut-être
difficile à croire au début, mais le compilateur est capable de résoudre directement
des problèmes pendant la compilation même. Grace aux templates, il est donc possible
de réaliser des calculs à la compilation.
Illustrons cela sans plus attendre par un premier exemple.
De manière générale dans les langages de programmation, la fonction mathématique
puissance est représenté par la fonction pow. Ainsi :
:::
pow(X, N) = X^N
Une telle fonction s'implémente de manière triviale avec une boucle :
:::cpp
unsigned long pow(unsigned long x, unsigned long n) {
unsigned long value = 1;
for (unsigned long i = 0; i < n; ++i) {
value *= x;
}
return value;
}
Cette version calcule donc une puissance durant l'exécution du programme. Pour notre part, nous allons utiliser des templates pour calculer une puissance à la compilation. Pour cela, nous allons utiliser la propriété récursive de la fonction puissance. En effet, formellement, la fonction puissance est définie ainsi :
:::
X^N = X * X^(N-1)
X^0 = 1
La fonction puissance est donc définie grace à une récursion qui s'arrête lorsque l'exposant arrive à 0.
Essayons donc d'exprimer cette définition en classe template :
:::cpp
template<int X, int N> struct Pow {
constexpr static int value = X * Pow<X, N-1>::value;
};
Très simplement, nous avons ici exprimé en classe template la récursion même (nous avons utilisé une structure au lieu d'une classe pour tirer parti de la propriété publique par défaut des éléments d'une structure)
Il ne reste donc plus qu'à exprimer la fin de la récursion lorsque N atteint
la valeur de 0. Pour cela, nous allons utiliser la spécialisation template.
En effet, les templates peuvent être spécialisés pour certaines valeurs, c'est
à dire que leur comportement peut-être redéfini pour certains types ou certaines
valeurs. Ainsi, nous allons spécialiser notre template Pow pour la valeur
de N à 0 :
:::cpp
template<int X> struct Pow<X, 0>
constexpr static int value = 1;
};
Lorsque N atteindra la valeur de 0, la récursion template s'arrêtera et la
valeur « retournée » sera ainsi de 1.
Nous pouvons désormais vérifier que tout fonctionne :
:::cpp
#include <iostream>
template<int X, int N> struct Pow {
static constexpr int value = X * Pow<X, N-1>::value;
};
template<int X> struct Pow<X, 0>
static constexpr int value = 1;
};
int main() {
int value = Pow<2, 4>::value;
std::cout << value << std::endl;
}
Pour fonctionner, ce programme doit être compilé avec le support de C++11 car
il utilise le nouveau mot-clé constexpr permettant de déclarer des valeurs
constantes à la compilation.
:::cpp
g++ -Wall -Werror -std=c++11 -O2 -o pow-templates pow-templates.cc
À l'exécution, la valeur 16 est donc bien affichée:
:::bash
$ ./pow-templates
$ 16
En guise de double-vérification, nous allons également vérifier que la constante 16 a bien été calculée à la compilateur et a bien été remplacée par le compilateur en examinant l'assembleur généré :
:::bash
objdump -M intel -d pow-templates
La section qui nous intéresse est la portion main de la section .text:
:::asm
00000000004006b0 <main>:
4006b0: 48 83 ec 08 sub rsp,0x8
4006b4: be 10 00 00 00 mov esi,0x10
4006b9: bf 60 10 60 00 mov edi,0x601060
4006be: e8 8d ff ff ff call 400650 <_ZNSolsEi@plt>
4006c3: 48 89 c7 mov rdi,rax
4006c6: e8 d5 ff ff ff call 4006a0 <_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@plt>
4006cb: 31 c0 xor eax,eax
4006cd: 48 83 c4 08 add rsp,0x8
4006d1: c3 ret
4006d2: 66 66 66 66 66 2e 0f data32 data32 data32 data32 nop WORD PTR cs:[rax+rax*1+0x0]
4006d9: 1f 84 00 00 00 00 00jk
À la deuxième ligne, on retrouve donc bel et bien notre constante 16 exprimée
en hexadécimal 0x10 qui est placée dans le registre esi. Le compilateur
a donc bel et bien calculé 2^4 à la compilation, fantastique !
Cet exemple, bien que simple dans l'esprit a donc permis de démontrer les techniques de base pour pouvoir effectuer des calculs et opérations à la compilation en utilisant les templates et la « récursivité ».
Nous sommes donc désormais prêts à passer aux choses sérieux et commencer à s'amuser avec les variadic templates
Voilà enfin venu le moment que vous attendiez impatiemment depuis le début de cet article. Ça a été long mais nous y sommes arrivés. Nous allons enfin pouvoir commencer à nous amuser pour de bon.
Jusqu'à présent, nos fonctions et classes templates comportaient un nombre fini
et déterminé de paramètres templates. Par exemple, la fonction Pow acceptait
deux paramètres templates.
Une classe de la bibliothèque standard comme std::map accepte quatre paramètres
templates: le type de la clé, le type de la valeur, la fonction de comparaison
permettant de comparer les éléments de la structure entre eux pour pouvoir
déterminer où les placer (map est une structure de type arbre rouge-noir) et
enfin l'allocateur dont le rôle est d'allouer les éléments en mémoire.
Tout cela pour dire qu'avant C++11, le nombre de paramètres templates devait être fini et connu à l'avance. C++11 a donc apporté une révision majeure aux templates en proposant des templates au nombre d'éléments infinis du nom de variadic templates.
Dans la bibliothèque, un des bénéfices des variadic templates se trouve avec la
classe std::tuple représentant une collection hétérogène de valeurs:
:::cpp
typedef std::tuple<std::string, double, double, double> Matrix3D;
Le type Matrix3D ci-dessus est donc un synonyme de type (typedef) pour un
tuple de quatres éléments. Le premier élément du tuple est de type std::string
et le reste du tuple est de type double.
Grace aux variadics templates, il est possible de stoquer un nombre indéfini
de valeurs dans un tuple.
La syntaxe proposée par C++11 pour définir une classe ou fonction template
variadic consiste à utiliser l'opérateur ellipse .... Cet opérateur étant
déjà utilisé pour les fonctions (par exemple printf), il a été repris pour les
templates:
:::cpp
template<typename ...Types> class Tuple {
};
typename ...Types est ainsi désigné un template parameter pack car il accepte
zéro ou plus paramètres templates. Un template variadic est donc un template avec
au moins un template parameter pack.
Ces packs de paramètres templates regroupant un ensemble de types sous un seul
nom, ceux-ci peuvent être « étendus » grace au même opérateur ellipse ... et
des règles bien précises. Le tableau ci-dessous résume les règles « d'extension »
des parameter packs :
| Expression | Expansion |
|---|---|
Types... |
Type1, Type2, Type3, ..., TypeN |
tuple<Types...> |
tuple<Type1, Type2, ..., TypeN> |
vector<Types>... |
vector<Type1>, vector<Type2>, ..., vector<Type3> |
Comme l'on peut le constater, le placement de l'opérateur ellipse ... peut
radicalement les règles d'extension des template parameter packs
Sans plus attendre, commençons par nous lancer en douceur dans la métaprogrammation avec les variadic templates.
Pour nous échauffer sans trop nous brusquer, nous allons commençons par un exemple
rudimentaire. Il est à noter que les exemples qui suivront nécessitent un compilateur
suffisamment récent pour implémenter l'ensemble des fonctionnalités. La version minimale
de gcc devant être utilisée est la version 4.7.
Nous allons donc dans un premier écrire un programme template permettant
de calculer la somme d'un ensemble de nombres entiers à la compilation de sorte
que l'assertion suivante soit vérifiée 5:
:::cpp
static_assert(Sum<1, 2, 3, 4, 5>::value == 1 + 2 + 3 + 4 + 5,
"Somme invalide");
Pour réussir cette implémentation, il est dans un premier temps nécessaire d'établir la relation d'une somme. Nous sommes chanceux car pour une somme, la récursion se définit de manière assez trivale:
:::
Sum([1, 2, 3]) = 1 + Sum([2, 3])
Sum([2, 3]) = 2 + Sum([3])
Sum([3]) = 3
En généralisant, la récursion devient la suivant:
:::
Sum([Head, Tail...]) = Head + Sum([Tail...])
Sum([Last]) = Last
Head représente la tête de liste et Tail... le reste des éléments de
la liste. La technique consiste donc à séparer les éléments d'une liste en
un couple d'éléments [Head, Tail...]
Commençons par définir notre variadic template:
:::cpp
template<int ...Numbers> struct SumImpl {
};
Les détails des implémentations seront gardés dans des structures au
suffixe Impl. SumImpl accepte donc en guise de paramètre template un ensemble
de nombres de type int.
Ceci étant fait, tachons désormais d'exprimer notre récursion. Dans l'état actuel,
des éléments sont manquants. En effet, pour exprimer la récursion template, nous
avons besoin de la tête de liste ainsi que du reste du élément. Pour cela, rien
de plus simple. Nous allons, une fois de plus, spécialiser notre variadic template
pour « découper » un pack de paramètres templates int ...Numbers en un
couple int Head, int ...Tail :
:::cpp
template<int Head, int ...Tail> struct SumImpl<Head, Tail...> {
static constexpr int value = Head + SumImpl<Tail...>::value;
};
À chaque étape de la récursion, on refait donc appel à SumImpl en étendant le
pack parameter Tail... afin de le re-diviser en couple Head, Tail....
Il ne nous reste plus qu'à exprimer la condition d'arrêt de notre récursion, lorsque la liste une fois étendue ne contient plus qu'un élément. Une fois encore, nous allons spécialiser notre template :
:::cpp
template<int Last> struct SumImpl<Last> {
static constexpr int value = Last;
};
Ce qui conclut notre implémentation. Une fois étendue, dès lors que la liste atteindra son dernier élément, la valeur de celui-ci sera « retournée » et la récursion prendra fin. Les valeurs précédemment calculées pourront donc être ajoutées les unes à la suite des autres, et tout celà à la compilation.
Pour disposer d'une implémentation complète, il ne nous reste plus qu'une dernière chose à réaliser: étendre les éléments au tout début de la récursion pour débuter la récursion. Pour cela, nous allons une fois de plus utiliser une nouvelle fonctionnalité de C++11 permettant de définir des synonymes templates (templates aliases) grace à la directive using :
:::cpp
template<int ...Numbers> using Sum = SumImpl<Numbers...>;
L'implémentation complète est la suivante :
:::cpp
#include <iostream>
template<int ...Numbers> struct SumImpl {
};
template<int Head, int ...Tail> struct SumImpl<Head, Tail...> {
static constexpr int value = Head + SumImpl<Tail...>::value;
};
template<int Last> struct SumImpl<Last> {
static constexpr int value = Last;
};
template<int ...Numbers> using Sum = SumImpl<Numbers ...>;
static_assert(Sum<1, 2, 3, 4, 5>::value == 1 + 2 + 3 + 4 + 5,
"Somme invalide");
int main() {
std::cout << Sum<1, 2, 3, 4, 5>::value << std::endl;
}
Encore une fois, on peut s'amuser à désassambler le binaire final pour vérifier
que l'expression Sum<1, 2, 3, 4, 5>::value a bien été remplacée à la
compilation par la valeur constante 15:
:::bash
$ objdump -M intel -d sum-templates
0000000000400690 <main>:
400690: 48 83 ec 08 sub rsp,0x8
400694: be 0f 00 00 00 mov esi,0xf
400699: bf 00 0c 60 00 mov edi,0x600c00
40069e: e8 8d ff ff ff call 400630 <_ZNSolsEi@plt>
4006a3: 48 89 c7 mov rdi,rax
4006a6: e8 d5 ff ff ff call 400680 <_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@plt>
4006ab: 31 c0 xor eax,eax
4006ad: 48 83 c4 08 add rsp,0x8
4006b1: c3 ret
4006b2: 66 66 66 66 66 2e 0f data32 data32 data32 data32 nop WORD PTR cs:[rax+rax*1+0x0]
4006b9: 1f 84 00 00 00 00 00
C'est bel et bien le cas, la valeur 15 exprimée en hexadémical 0xf a bien été
calculée par le compilateur, il n'a pas fini de nous étonner !
Grace à ce premier exemple, on a donc pu appréhender les techniques de base pour jouer avec les variadic templates. Intéressons-nous maintenant à un exemple plus utile et réel
Certains algorithmes (par exemple de somme de contrôle) nécessitent de travailler directement sur les valeurs binaires. Ce cas concrêt va consister à fournir une implémentation permettant d'inverser un nombre indéterminé de bits d'une donnée entière, de sorte à pouvoir écrire le code suivant :
:::cpp
int value = 140;
flip_bits<1, 5, 8>(value);
Au terme de la compilation, les bits numéro 1, 5 et 8 de value seront donc inversés.
Nous allons dans un premier temps commencer par les préparatifs. Pour réussir
cette implémentation, il nous faut déjà trouver comment inverser un certain bit
d'un ou plusieurs octets. Rien de plus facile. Parmi l'ensemble des fonctions
binaires, la fonction xor réalise un ou exclusif. En C++, le ou exclusif se
réalise avec l'opérateur ^. Pour comprendre l'intérêt de cette fonction,
commençons par regarder la table de vérité du ou exclusif:
| A | B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
La fonction ou exclusif retourne 0 si les deux bits sont identiques. En se basant sur la table de vérité, on comprend que pour inverse un bit N d'un octet, il suffit de faire un ou exclusif avec la valeur 1.
Grace à cela, on peut commencer à écrire une fonction simple permettant d'inverser un simple bit N d'une série d'octets :
:::cpp
template<size_t Bit, typename Data>
typename std::enable_if<std::is_integral<Data>::value, void>::type
flip_bit(Data &data) {
static_assert(Bit < sizeof(Data) * CHAR_BIT,
"Bit number out of range");
data ^= (1 << Bit);
}
Ce premier fragment de code est légèrement plus complexe que ce à ce que l'on aurait pu s'attendre. Décortiquons ensemble les pièces du puzzle en commençant par le cryptique type de retour :
:::cpp
typename std::enable_if<std::is_integral<Data>::value, void>::type
Ceci est une pratique habituelle de méta-programmation permettant d'activer la fonction à la compilation selon une certaine condition. La condition en question est ici exprimée par
:::cpp
std::is_integral<Data>::value
std::is_integral est ce que l'on appelle une classe de traits. En C++, cela
deśigne une classe (ou structure) qui permet d'associer des informations sur un
autre type. En l'occurence, le trait is_integral permet d'associer l'information
suivante au type:
:::
Le type est-il un type intégral ? Un type est considéré comme intégral s'il
fait partie de la liste char, bool, int, long, long long
Souhaitant restreindre notre fonction aux types entiers uniquement, nous la rendons
visible grace std::enable_if uniquement si le type de Data est intégral.
Si Data n'est pas intégral, la fonction sera « supprimée » et ne pourra pas être
appelée, provoquant une erreur à la compilation. Sinon, elle retournera void.
:::cpp
static_assert(Bit < sizeof(Data) * CHAR_BIT,
"Bit number out of range");
L'assertion statique permet ensuite de vérifier, à la compilation, que le Bit
transmis n'est pas hors des limites. Cette assertion fonctionne en vérifiant que
le numéro du bit transmis est bien inférieur au nombre total de bits du type
Data. Le nombre total de bits est récupéré en multipliant la taille du type
Data en byte (retourné par l'opérateur sizeof) par le nombre de bits présents
dans un byte (représenté par la constante CHAR_BIT).
En cas de dépassement, un message d'erreur sera émis à la compilation. Cela
constitue également un avantage à la méta-programmation: pouvoir effectuer des
vérifications pendant la compilation et ainsi signaler les erreurs au plus
tôt.
À partir de cette base, nous allons commencer à batir notre récursion. Pour
cela, nous allons écrire un template variadic FlipBitsImpl qui comportera
une méthode statique flip comportant la logique de la récursion :
:::cpp
template<typename Data, size_t Bit, size_t ...Rest>
struct FlipBitsImpl {
static void flip(Data &data) {
flip_bit<Bit>(data);
FlipBitsImpl<Data, Rest...>::flip(data);
}
};
À chaque tour de récursion, on inverse donc le bit courant grace à la fonction
que nous venons d'écrire puis on continue la récursion avec le reste des
bits en étendant le pack de paramètres Rest...
Finissons donc notre implémentation par la condition d'arrêt de la récursion lorsque le dernier bit est atteint:
:::cpp
template<typename Data, size_t Bit>
struct FlipBitsImpl<Data, Bit> {
static void flip(Data &data) {
flip_bit<Bit>(data);
}
};
Un dernier synonyme template pour cacher l'implémentation et le tour est joué :
:::cpp
template<typename Data, size_t ...Bits>
using FlipBits = FlipBitsImpl<Data, Bits...>;
Mais ce n'est pas encore complètement terminé. Pour enfin compléter l'implémentation, il nous reste une dernière chose à faire: fournir une fonction qui sera plus pratique qu'appeler nous-même le template:
:::cpp
template<size_t ...Bits, typename Data>
void
flip_bits(Data &data) {
FlipBits<Data, Bits...>::flip(data);
}
L'avantage de la fonction est que le type de Data sera automatiquement déduit 6
par le compilateur, évitant ainsi d'avoir à le spécifier soit-même lors de
l'appel à la fonction flip_bits et au template FlipBits.
Assez cool non ? Auriez-vous imaginé pouvoir faire tout cela à la compilation ? Et bien c'est maintenant chose faite.
Mais attendez, vous en voulez encore ? Allez, je vous l'accorde, un petit dernier pour la route.
Puisqu'on y est, nous allons rester dans le binaire mais nous allons cette fois-ci essayer de convertir un nombre binaire en décimal à la compilation. Cet exemple sera sans doute le plus complexe, il faudra donc faire un dernier effort.
Le C++ ne donnant pas la possibilité d'écrire des constantes binaires du style
0b1000101, nous allons nous même faire notre propre mécanisme pour contourner
cela. Et devinez quoi ? Nous allons utiliser les variadic templates, une fois
de plus. Cependant, nous allons rajouter une difficulté supplémentaire car, après
tout, on commence à être à l'aise.
Attention, ça va aller très vite. À la fin, notre implémentation devra permettre
de ne pas déclencher les assertions suivantes :
:::cpp
static_assert(BinaryConverter<const int, 0>::value == 0, "0b != 0");
static_assert(BinaryConverter<int, 0, 1, 1, 1>::value == 7, "0111b != 7");
static_assert(BinaryConverter<int, 1, 0, 1, 1>::value == 11, "1011b != 11");
static_assert(BinaryConverter<char, '0'>::value == 0, "0b != 0");
static_assert(BinaryConverter<const char, '0','1', '1', '1'>::value == 7, "0111b != 7");
static_assert(BinaryConverter<char, '1', '0', '1', '1'>::value == 11, "1011b != 11");
Vous êtes prêts ? C'est parti.
Cette fois-ci, notre approche va être légèrement différente. Pour calculer le résultat, nous allons au fur et à mesure passer le résultat intermédiaire à l'intérieur d'un paramètre template :
:::cpp
template<unsigned Result, typename Vals, Vals ...digits>
struct BinaryConverterBase {
}
Le premier paramètre template correspond donc au résultat qui sera progressivement
calculé pendant la récursion. le second paramètre correspond au type des valeurs
qui vont suivre (int ou char) et le dernier paramètre est un pack de paramètres
désignant les valeurs des bits à convertir.
D'autre part, nous avons utilisé la notation BinaryConverterBase plutôt que
BinaryConverterImpl pour une raison bien particulière que nous verrons à la fin.
La récursion va demander quelques éléments supplémentaires. Tout d'abord, toujours
dans notre optique de sécurité, nous souhaitons vérifier qu'aucun chiffre non-binaire
autre que 0 ou 1 n'est passé en paramètre. Pour celà, nous allons écrire une
fonction is_binary retournant un booléen indiquant si la valeur est booléenne
ou non. Manipulant des entiers aussi bien que des caractères, nous allons respectivement
avoir besoin de deux surcharges de cette fonction. Enfin, pour séparer les logiques,
nous allons garder cela dans un espace de noms séparé details :
:::cpp
namespace details {
constexpr bool is_binary(int d) {
return d == 0 || d == 1;
}
constexpr bool is_binary(char c) {
return is_binary(c - '0');
}
}
Pour une valeur de type char, nous utilisons le fait qu'en C++ il est garanti
que l'expression suivante soit vrai: '0' + 1 == '1' pour convertir le
caractère en chiffre.
Enfin, nous allons également avoir besoin d'un utilitaire de « conversion » pour
convertir une valeur de type char '0' en valeur décimale 0 et '1' en 1.
Pour cela, nous allons écrire un utilitaire template et fournir deux spécialisations
pour les types char et int:
:::cpp
namespace details {
template<typename T> struct DigitValue {
};
template<> struct DigitValue<int> {
static constexpr int v(const int value) { return value; }
};
template<> struct DigitValue<char> {
static constexpr int v(const char value) { return value - '0'; }
};
constexpr bool is_binary(int d) {
return d == 0 || d == 1;
}
constexpr bool is_binary(char c) {
return is_binary(c - '0');
}
}
Nous sommes désormais prêts à implémenter notre récursion. Comme d'habitude, nous
découpant notre pack de paramètres templates en couple Head, Tail... pour
pouvoir agir sur la tête de liste et continuer la récursion avec le reste :
:::cpp
template<unsigned Result, typename Vals, Vals Head, Vals ...Tail>
struct BinaryConverterBase<Result, Vals, Head, Tail...> {
static_assert(details::is_binary(Head), "Encoutered a non-binary value (must be either 0 or 1)");
static constexpr unsigned value = BinaryConverterBase<2 * Result + details::DigitValue<Vals>::v(Head),
Vals, Tail...>::value;
};
À chaque étape de récursion, nous nous efforçons également de vérifier que la valeur est bien binaire grace à notre fonction is_binary.
L'étape finale de la récursion s'arrête lorsque tous les nombres ont été « consommés », auquel cas le résultat correspond à la valeur finale :
:::cpp
template<unsigned Result, typename Vals> struct BinaryConverterBase<Result, Vals> {
static constexpr unsigned value = Result;
};
Il ne nous reste donc plus qu'à débuter la récursion. Cependant, cette fois-ci
nous n'allons pas utiliser de synonyme template avec la directive using mais
une relation simple d'héritage :
:::cpp
template<typename T, T ...digits> struct BinaryConverter :
public BinaryConverterBase<0, typename std::remove_cv<T>::type, digits...>
{
typedef typename std::remove_cv<T>::type type;
static_assert(std::is_same<type, int>::value || std::is_same<type, char>::value,
"Supported types are int and char");
};
Tout cela pour la simple et bonne raison que nous avons besoin de mettre une machinerie template supplémentaire. La subtilité se trouve dans la ligne suivante:
:::cpp
typename std::remove_cv<T>::type
std::remove_cv fait également des classes de trait de la bibliothèque standard
du langage donc le but est de tout simplement supprimer les qualificateurs
const et volatile d'un type T, permettant ainsi de transformer const int
en int et const char en char. Cela nous permet de « normaliser » le type
et vérifier à la compilation qu'il s'agit bien d'un entier int ou char.
Mais ne nous arrêtons pas en si bon chemin. Précédemment, nous avons dit que C++
n'autorisait pas à écrire des constantes binaires du type 0b110101. Cependant,
C++11 a introduit une nouvelle fonctionnalité du nom de user defined literals
permettant d'ajouter des suffixes personnalisés à des valeurs litérales constantes
pour calculer une certaine valeur.
Nous pouvons utiliser cette nouvelle fonctionnalité pour nous même implémenter les constantes litérales binaires en C++, de sorte à pouvoir écrire :
:::cpp
const int value = 10011101_b;
Le suffixe _b indiquant une valeur binaire. Pour cela, il suffit de fournir
un opérateur un peu spécial :
:::cpp
template<char ...digits> constexpr unsigned operator"" _b() {
return BinaryConverter<char, digits...>::value;
}
Ainsi, lorsque nous écrirons 10011101_b, la fonction operator "" _b sera
invoquée et nous pourrons utiliser notre machinerie de conversion binaire à
la compilation pour réaliser le calcul. Impressionnant, n'est-ce pas ?
Voici donc le programme complet :
:::cpp
#include <iostream>
#include <type_traits>
#include <cassert>
namespace details {
template<typename T> struct DigitValue {
};
template<> struct DigitValue<int> {
static constexpr int v(const int value) { return value; }
};
template<> struct DigitValue<char> {
static constexpr int v(const char value) { return value - '0'; }
};
constexpr bool is_binary(int d) {
return d == 0 || d == 1;
}
constexpr bool is_binary(char c) {
return is_binary(c - '0');
}
}
template<unsigned Result, typename Vals, Vals ...digits> struct BinaryConverterBase {
};
template<unsigned Result, typename Vals, Vals Head, Vals ...Tail>
struct BinaryConverterBase<Result, Vals, Head, Tail...> {
static_assert(details::is_binary(Head), "Encoutered a non-binary value (must be either 0 or 1)");
static constexpr unsigned value = BinaryConverterBase<2 * Result + details::DigitValue<Vals>::v(Head),
Vals, Tail...>::value;
};
template<unsigned Result, typename Vals> struct BinaryConverterBase<Result, Vals> {
static constexpr unsigned value = Result;
};
template<typename T, T ...digits> struct BinaryConverter :
public BinaryConverterBase<0, typename std::remove_cv<T>::type, digits...>
{
typedef typename std::remove_cv<T>::type type;
static_assert(std::is_same<type, int>::value || std::is_same<type, char>::value,
"Supported types are int and char");
};
template<char ...digits> constexpr unsigned operator"" _b() {
return BinaryConverter<char, digits...>::value;
}
static_assert(BinaryConverter<const int, 0>::value == 0, "0b != 0");
static_assert(BinaryConverter<int, 0, 1, 1, 1>::value == 7, "0111b != 7");
static_assert(BinaryConverter<int, 1, 0, 1, 1>::value == 11, "1011b != 11");
static_assert(BinaryConverter<char, '0'>::value == 0, "0b != 0");
static_assert(BinaryConverter<const char, '0','1', '1', '1'>::value == 7, "0111b != 7");
static_assert(BinaryConverter<char, '1', '0', '1', '1'>::value == 11, "1011b != 11");
int main() {
assert(0111_b == 0x7);
assert(11111111_b == 0xFF);
assert(10101010_b == 0xAA);
}
Cette fois-ci, je vous laisse vérifier par vous-même l'assembleur généré par le compilateur
Au travers de divers exemples, nous avons donc pu explorer les possibilités de méta-programmation offertes par les templates du C++. Outre l'aspect générécité, nous avons donc pu voir que les templates pouvaient servir à réel écrire et générer du code à la compilation.
De plus, C++11 et les variadic templates ont permis d'étendre encore plus les possibilités de méta-programmaton, rendant l'exercice encore plus complexe mais pas moins stimulant et intéressant.
Également, nous avons pu, au sein de cet article, découvrir de nouvelles
fonctionnalités de C++11 comme le mot-clé constexpr, les assertions statiques
avec static_assert ou encore les user defined literals. C++11 n'est donc
pas une révision mineure du langage mais a bel et bien redonné un coup de jeune
au langage. La liste des nouvelles fonctionnalités est encore bien plus longue
et vaut également le coup d'oeil.
Au terme de cet article, j'espère donc ne pas avoir provoqué une overdose de templates et j'espère vous avoir convaincu de leur réel pouvoir.
Footnotes
-
Une liste plus exhaustive peut-être retrouvée sur wikipedia ↩
-
il se trouve que cette fonction existe déjà dans la bibliothèque standard ↩
-
Les templates imposent très souvent des contraintes implicites sur les types comme par exemple le fait pour un type T d'être copiable (disposer d'un constructeur de copie) ↩
-
size_t correspond à un type entier non signé ↩
-
static_assertest une autre des nouveautés de C++11 et permet de poser des assertions durant la compilation. À la compilation, si l'évaluation de la condition est fausse, alors le compilateur reporte le message d'assertion. ↩ -
C'est ce qui s'appelle template argument deduction ↩