III. Quel parti tirer des templates variadiques ? Quatre exemples▲
III-A. Remplacer les mécanismes variadiques hérités du C: printf, la sécurité en plus▲
C'est une des raisons pour lesquelles le C++ a été créé : il était un peu trop facile, aux yeux de Bjarne Stroustrup, de faire des horreurs en C. Les casts trop fréquents, la gestion trop explicite de la mémoire, l'absence de gestion des exceptions et… les macros et fonctions variadiques.
Il est vrai que printf a été une source d'erreurs et de vulnérabilités. Un défaut dans la vérification des arguments, à un endroit ou l'autre du programme, peut ouvrir la porte à une action malveillante : ces vulnérabilités étaient fréquentes il y a encore quelques années au point d'avoir leur propre nom, en anglais format string exploits. Grâce aux templates variadiques, il est désormais possible d'être certain que le nombre d'arguments et leur type ne prendra pas le programme par surprise.
En voici une implémentation basique ; c'est l'occasion pour vous familiariser avec deux grandes techniques pour exploiter les templates variadiques : la récursion et le pattern matching.
Comme vous le savez bien, une fonction récursive est une fonction qui s'appelle elle-même. Lorsqu'une fonction est paramétrée par un template variadique, l'astuce consiste à ce qu'elle s'appelle elle-même, mais paramétrée avec un argument de moins dans le template variadique, puis un autre argument de moins, jusqu'à ce qu'il n'en reste plus.
Le cas de base, qui termine la récursion, est donc le cas où il n'y a plus d'argument template. Pour notre fonction printf, il ne reste plus que la chaîne de format. Si, alors qu'il ne reste plus qu'une chaîne de format, celle-ci fait encore référence à des arguments à afficher, c'est qu'elle est mal formée, ou qu'il y a une erreur dans l'appel de la fonction.
2.
3.
4.
5.
6.
7.
void printf(const char* format) { // cas de base : il n'y a qu'une chaîne de format
while (*format) {
if (*format == '%' && *++format != '%') // %% == % (pas une directive)
throw std::invalid_argument("Pas assez d'arguments !\n");
std::cout << *format++;
}
}
Vous voyez que nous pouvons prédire ce qui se passera s'il n'y a pas assez d'arguments : une exception sera levée. Dans le cas de printf en C, le comportement de la fonction est non défini.
Maintenant pour le cas général : regardez bien la signature template, qui fait usage du pattern matching : le parameter pack a été scindé en un Arg d'un côté, des Args de l'autre. Cela nous permet d'isoler le premier argument, qui sera utilisé lors de cet appel, et de nommer un parameter pack qui contient les suivants :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
template <typename Arg, typename... Args>
void printf(const char* format, Arg arg, Args... args) {
while (*format) {
if (*format == '%' && *++format != '%') {
std::cout << arg; // déduit tout seul le type d'argument
return printf(++format, args...); // la récursion, arg en moins
}
std::cout << *format++;
} // on a fini la chaîne de format et il nous reste des arguments : throw
throw std::invalid_argument("Too many arguments for printf\n");
}
Je vous avais promis également de vérifier le type des arguments… mais pas besoin d'écrire une ligne de code pour ça ! Comme l'opérateur << est lui-même un template, il détecte tout seul le type des arguments qui lui arrivent !
Il est possible, cependant, de faire des vérifications plus poussées et surtout de les faire lors de la compilation, grâce à une autre nouveauté du standard C++11, le qualificateur constexpr. Je vous conseille, si le sujet vous intéresse, la lecture de cet article. Vérifier la concordance des types passés en argument avec la chaîne de format est également faisable. Pour donner une idée :
2.
3.
4.
5.
6.
7.
template <typename Arg, typename... Args>
void printf(const char* format, Arg arg, Args… args) {
…
switch(current_format_qualifier) {
case 'd' : if ( ! is_integral<Arg>() ) throw std::invalid_argument() ;
…
}
III-B. Vérifier l'adhésion des paramètres template à un concept : assertion statique et opérateur de fonction▲
Une nouvelle évolution du standard est en cours de rédaction. Les concepts devraient faire leur apparition au sein du langage (aujourd'hui, ils n'existent que dans la documentation). Ils permettront d'indiquer ce qui est attendu d'un paramètre template de façon claire et uniforme. Par exemple, le concept pourra indiquer qu'un type template nommé Iterator doit être : 1) un itérateur, 2) de type random_iterator et 3) pointant sur des valeurs intégrales.
Pour l'instant, les outils qui permettent de vérifier des préconditions sur les types employés sont plus frustes. Ils reposent sur des bibliothèques de « traits » dont le résultat est vérifié lors de la compilation. Mettons que l'on veuille vérifier si le type donné est bien un type entier :
2.
3.
4.
5.
6.
7.
#include <type_traits>
template <typename Integer>
Integer modulo(Integer a, Integer b) {
static_assert(std::is_integral<Integer>::value, " Integer doit être un type entier ! ") ;
…
}
Les bibliothèques de « traits » sont bien fournies mais, bien sûr, comportent des lacunes. Pour certaines conditions, il nous faut fournir notre propre « trait ».
Nous allons élaborer un « trait » qui nous permet de vérifier si le type reçu est bien un foncteur :
2.
template <typename T, typename... Args>
struct is_functor ;
Pour une analyse plus détaillée et plus progressive des techniques à l'œuvre, je vous renvoie à un article précédent : SFINAE, un exemple d'implémentation. Grâce aux templates variadiques, il sera possible de généraliser l'exemple de cet article, qui ne vérifiait que l'existence d'un opérateur de fonction à un argument.
Voilà d'abord le cas de base, celui qui ne sera instancié par le compilateur qu'à défaut d'une signature plus précise :
2.
3.
constexpr auto _has_func_operator(...) { // c'est la signature la moins déterminée
return false; // donc la moins attirante
}
Nous fournissons ensuite au compilateur une signature qui correspond à ce que nous cherchons, un type qui a un opérateur de fonction. Attention les yeux ! Mais rien de si compliqué une fois la panique passée :
2.
3.
4.
5.
template <typename Type, typename... Args>
constexpr auto _has_func_operator(int)
-> decltype(std::declval<Type>()(std::declval<Args>()...), bool()) {
return true;
}
On décortique :
_has_func_operatorprend un inten argument : cette signature sera préférée par le compilateur, sauf si elle est mal formée, c'est-à-dire qu'il y a une erreur dans sa définition. L'erreur se trouverait (c'est intentionnel) dans la définition de son type de retour : decltype(std::declval<Type>()(std::declval<Args>()...), bool()).
Le type de retour pourrait être énoncé plus simplement : decltype(Type()(Args()…), bool()). decltype permet de demander au compilateur de déduire un type à partir d'une expression.
decltype a des subtilités qu'il faut connaître avant de l'employer. Si vous comptez en faire un usage intensif, je vous invite à jeter un œil à la référence!
Cette expression-là est organisée autour de l'opérateur « virgule » : les deux opérandes seront évalués, mais c'est celui de droite qui sera renvoyé. Comme nous le voulons, c'est un booléen qui sera renvoyé par la fonction, pour indiquer si un opérateur de fonction est bien présent.
Mais nous voulons voir aussi si le type de l'expression Type()(Args()…) est correct. S'il est correct, c'est que Type a bien un opérateur de fonction, et un opérateur de fonction avec n'importe quel nombre de paramètres !
Reste à expliquer le rôle de std::declval<Type>(): il permet, au moment de la compilation, de retourner une référence vers un objet Type sans avoir à construire celui-ci ; il permet de gérer le cas où le foncteur n'a pas de constructeur -c'est le cas d'une lambda, par exemple.
Remarquez également où se trouve l'opérateur ellipse, à droite des parenthèses de std::declval<Args>()… L'expression sera donc développée en :
std::declval<Type>()(std::declval<Arg1>(), std::declval<Arg2>(), …, std::declval<ArgN>())
Reste à envelopper ces deux fonctions pour en faire un « trait » bien élevé respectant l'interface de la STL :
2.
3.
4.
template <typename Type, typename... Args>
struct is_functor{
static constexpr bool value = _has_func_operator<Type, Args...>(0);
};
On invoque _has_func_operator avec l'argument 0 : si Type a bien un opérateur de fonction, le compilateur utilisera la surcharge qui prend un int en argument et renvoie true; sinon il se rabattra sur celle qui a une signature générique. Notez bien que ces deux surcharges sont constexpr, et peuvent donc être appelées à la compilation.
III-C. Générer des séquences d'entiers à la compilation▲
Voici un troisième exemple d'utilisation des templates variadiques. L'intérêt n'en apparaît pas immédiatement : il s'agit de générer des séquences d'entiers telles que { 0, 1, 2, … , N } à la compilation. On a beaucoup plus souvent besoin de ce genre de séquences qu'on ne pourrait le penser ; j'en donnerai une illustration dans le quatrième exemple, quand nous verrons ensemble comment trier de façon extrêmement rapide un tableau de petite dimension.
Je présenterai deux méthodes d'implémentation : la première, la récursion par héritage, est très proche des techniques développées par Alexei Alexandrescu pour ses Type_lists. Elle a l'avantage d'être entièrement compatible avec le standard C++11 ; la seconde, au contraire, ne devient lisible qu'avec le standard C++14 mais elle a plus d'avenir car elle est plus claire et plus concise, en un mot plus élégante.
III-C-1. La méthode de récursion par héritage▲
Cet exemple met en œuvre une autre technique de récursion que celle que nous avons vue tout à l'heure : c'est la récursion par héritage. Quelques lignes de code permettront de mieux voir de quoi il s'agit.
Nous commençons par définir une structure pour accueillir une liste d'entiers connus à la compilation :
2.
3.
4.
template <long unsigned int... Ns> // voilà nos entiers
struct Index_vector {
using type = Index_vector<Ns...>; // l'utilité de cet alias apparaîtra plus tard...
};
Cette liste peut être vide ou comporter un ou plusieurs éléments. Comment fait-on pour ajouter un élément à la liste ? Voici un premier exemple de récursion par héritage :
2.
3.
4.
5.
template <typename Index_vector, long unsigned int N>
struct Push_front; // la signature à spécialiser
template <long unsigned int... Ns, long unsigned int N> // la spécialisation
struct Push_front<Index_vector<Ns...>, N> : Index_vector<N, Ns...> {};
Push_front hérite de Index_vector, auquel il a rajouté un élément. Comme il hérite de Index_vector, l'alias que définit Index_vector lui est accessible :
2.
3.
using deux_trois = Index_vector<2,3> ;
using un_deux_trois = Push_front<deux_trois, 1> ;
// typename un_deux_trois::type == Index_vector<1,2,3>
Et voilà, nous avons ajouté un membre à la liste d'entiers !
Reste à généraliser pour obtenir une séquence. Nous utiliserons la même méthode de récursion par héritage. Nous commençons une fois de plus par le cas d'arrêt, ou cas de base :
Je commence par le cas de base car il est le plus simple. Dans le code, pour satisfaire le compilateur, il faut toujours déclarer les spécialisations comme celle-ci après la signature générale.
2.
3.
// Le terme à ajouter est 0, c'est la fin de la séquence
template <typename Index_vector>
struct Range<0, Index_vector> : Push_front<Index_vector, 0>::type {};
Et maintenant le cas général :
2.
3.
// !! le deuxième paramètre est par défaut un Index_vector vide
template <long unsigned int rangesz, typename Index_vector = Index_vector<> >
struct Range : Range<rangesz-1, typename Push_front<Index_vector, rangesz>::type > {};
Essayons de démêler un peu tout ça :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
Range<5> r5 ; // <=> Range<5, Index_vector<>> grâce au template par défaut
// hérite de :
Range<5-1, typename Push_front<Index_vector<>, 5>> //qui
// hérite de
Range<4-1, typename Push_front<Index_vector<5>, 4>> // qui
//hérite de
Range<3-1, typename Push_front<Index_vector<4,5>, 3>>
// …
// hérite de :
Range<0, typename Push_front<5,4,3,2>, 1>>
// hérite de (cas d'arrêt) :
Push_front<Index_vector<5,4,3,2,1>, 0>
// qui définit un alias Index_vector<5,4,3,2,1,0> !
Voilà notre liste d'entiers constituée ! Il y avait une solution beaucoup plus facile, utiliser la bibliothèque standard… Mais il vous faut pouvoir utiliser la version C++14.
III-C-2. La méthode C++14 : auto et fonctions constexpr▲
Le standard C++14 permet, grâce au seul mot-clé auto, de déduire le type de retour d'une fonction. Les capacités de déduction sont limitées, en particulier l'usage de la récursion. En C++11, le même mot-clé pouvait être utilisé mais en conjonction avec decltype:
2.
3.
4.
5.
6.
7.
8.
// C++11
auto func(int i) -> decltype(i) {
return i ;
}
// C++14
auto func(int i) {
return i ;
}
Cette nouvelle possibilité permet une méta-programmation plus élégante en conjonction avec le mot-clé constexpr, qui définit des fonctions pouvant être appelées lors du processus de compilation. constexpr peut également être utilisé pour définir des variables utilisables à la compilation, par exemple, comme paramètre d'un template.
Le mot-clé constexpr mériterait un article à part entière, mais son utilisation dans l'exemple qui vient est assez intuitive.
La dernière brique pour comprendre l'exemple suivant est une nouveauté C++14 de la bibliothèque standard : template <std::size_t… Ns> std::index_sequence, dont la définition est très proche de Index_vector. Sa définition pourrait être :
2.
3.
4.
Namespace std {
template <std::size_t... Ns>
struct index_sequence {} ;
}
Commençons par une courte fonction constexpr qui décrémente une index_sequence composée d'un seul nombre :
2.
3.
4.
template <std::size_t N>
constexpr auto operator--(std::index_sequence<N>) {
return std::index_sequence<N-1>();
}
L'index_sequence dans cet exemple est composée d'une seule valeur, diminuée dans le type de retour de la fonction. Cet exemple aurait pu être écrit en C++11, à condition d'implémenter soi-même std::index_sequence, car le type de retour est simple à définir. Lorsque nous avancerons dans les étapes de notre méta-programme, la flexibilité donnée par le mot-clé auto deviendra indispensable. Venons-en à la construction de notre range :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
// le cas de base : il doit être défini en premier. Il prend en premier argument une valeur de type std::index_sequence<0> qui marque la fin de la récursion
template <std::size_t... Ns>
constexpr auto build_range(std::index_sequence<0>, std::index_sequence<Ns...>) {
return std::index_sequence<0, Ns...>();
}
// le cas général : remarquez l'utilisation de l'opérateur de décrémentation défini dans l'exemple précédent
template <std::size_t N, std::size_t... Ns>
constexpr auto build_range(std::index_sequence<N> n, std::index_sequence<Ns...>) {
return build_range_impl(--n, std::index_sequence<N, Ns...>());
}
Le standard C++14 est plus ou moins bien implémenté selon les compilateurs. Ce code a été compilé avec gcc 5 ; la version 4.9 le refusait.
Le code est plus concis et, à mon avis, plus lisible : il ressemble plus à de la programmation classique et est donc moins ésotérique pour des yeux peu habitués à la méta-programmation.
III-C-3. Un exemple d'utilisation▲
Une liste d'entiers générée à la compilation est d'usage fréquent en méta-programmation. Pour donner un exemple digne d'intérêt, elle permet d'appeler une fonction qui exige n arguments en lui fournissant un tuple contenant n éléments :
2.
3.
4.
5.
6.
7.
8.
9.
10.
template <typename Fn, typename... Args, std::size_t... Idx>
decltype(auto) call_with_tuple_impl(Fn fn, const std::tuple<Args...>& targs, Index_vector<Idx...>&&) {
return fn(std::get<Idx>(targs)...);
}
template <typename Fn, typename... Args>
decltype(auto) call_with_tuple(Fn fn, const std::tuple<Args...>& targs)
{
return call_with_tuple_impl(fn, targs, Range<sizeof...(Args)-1>());
}
III-C-4. Fusionner deux ranges▲
À la C++11 :
Avant d'en arriver à notre algorithme de tri à la compilation, il nous faut bien saisir une technique supplémentaire, qui consiste à surparamétrer une spécialisation de template (relisez deux ou trois fois la phrase, si ce n'est toujours pas clair, cela viendra avec l'exemple). Nous l'utiliserons pour fusionner deux séquences.
Nous prenons d'abord une structure template, mais nous ne la définirons même pas, elle n'est là que pour être spécialisée :
2.
template <typename IV1, typename IV2>
struct Join_ranges; // même pas définie, juste déclarée
La spécialisation template nous permet de récupérer les séquences dans les entrailles des séquences à fusionner :
2.
template <long unsigned int... lhs, long unsigned int... rhs>
struct Join_ranges<Index_vector<lhs...>, Index_vector<rhs...>> : Index_vector<lhs..., rhs...> {};
Une fois que l'on a compris, c'est simple. Mais pas avant ! Cela va nous permettre un tri ultra-rapide.
À la C++14 :
Encore une fois, la méthode C++14 est plus concise et plus élégante :
2.
3.
4.
template <std::size_t... Ms, std::size_t... Ns>
constexpr auto join(const std::index_sequence<Ms...>, std::index_sequence<Ns...>) {
return std::index_sequence<Ms..., Ns...>();
}
III-D. Optimiser le code : dérouler les boucles à la compilation pour un tri optimal▲
Un petit rappel pour commencer : est-ce que vous vous souvenez du tri-bulle, un des algorithmes de tri les plus simples et les moins efficaces ? C'est celui que nous allons utiliser. Ne soyez pas déçus. Si sa complexité asymptotique est très élevée (quadratique), nous allons compenser. La complexité d'un algorithme peut-être représentée comme le produit d'une constante (le nombre d'opérations requises par une étape) et le nombre d'étapes. Un tri comme qsort a une complexité c . N log N, où c est la constante. Pour le tri-bulle, la complexité est de c . N². L'idée est que pour un petit N, le poids de la constante joue plus. Nous allons donc écrire une optimisation du tri-bulle où la constante est la plus petite possible. Pour cela, la meilleure solution est de dérouler la boucle à la compilation. C'est la raison pour laquelle nous choisissons le tri-bulle, les boucles sont connues à la compilation :
2.
3.
4.
5.
6.
// tri bulle sans fioritures
for (int i = tabsize-1 ; i ≥ 0 ; --i) {
for (int j = 0 ; j < i ; ++j) {
if (tab[j+1] < tab[j]) std::swap(tab[j], tab[j+1]) ;
}
}
La séquence à dérouler, pour un tableau de cinq éléments, est donc : 0, 1, 2, 3, 4, 0, 1, 2, 3, 0, 1, 2, 0, 1, 0. Nous allons utiliser nos capacités acquises à générer des séquences et à les joindre entre elles.
III-D-1. La méthode C++11▲
2.
3.
4.
5.
6.
7.
// le cas d'arrêt : on est arrivés à 0
template <>
struct Bubble_ranges<0> : Range<0> {};
// le cas général : on joint par récursion-héritage une séquence N avec une BubbleRange N-1
template <long unsigned int N>
struct Bubble_ranges : Join_ranges<typename Range<N>::type, typename Bubble_ranges<N-1>::type> {};
Si l'on développe cela, comme nous l'avons fait pour montrer la génération de Range, cela donne :
2.
3.
4.
5.
6.
7.
8.
9.
Bubble_ranges<4> ; // qui hérite de
Join_ranges<typename Range<4>::type, typename Bubble_ranges<4-1>::type>
// <=> Join_ranges<Index_vector<0,1,2,3,4>, typename Bubble_ranges<3>::type>
// or Bubble_ranges<3> hérite de
Join_ranges<Index_vector<0,1,2,3>, typename Bubble_range<2>::type>
// …
Bubble_ranges<O> ; // qui hérite de Range<0>, soit IndexVector<0>
// on pourrait aussi exprimer ce développement comme :
Join_ranges<Index_vector<0,1,2,3,4>, Join_ranges<Index_vector<0,1,2,3>, Join_ranges<Index_vector<0,1,2>, Join_ranges<Index_vector<0,1>, Index_vector<0>>>>>
Bien, nous avons notre séquence d'indices. Avant de chercher à la dérouler pour faire un tri, il nous faut tout de même une fonction de comparaison qui échange les valeurs à l'indice i et i+1 si nécessaire :
2.
3.
4.
5.
template <class T, long unsigned int N>
int swap_if_less(std::array<T, N>& array, const long unsigned int i) {
if (array[i+1] < array[i]) std::swap(array[i+1], array[i]);
return 0;
}
Remarquez la signature un peu spéciale pour une fonction de tri : nous prenons comme argument un tableau et un index et nous renvoyons toujours 0. L'utilité en sera visible un peu plus loin.
Remarquez aussi que nous trions des std::array, qui ont l'avantage inestimable -et dans notre cas, parfaitement nécessaire- d'avoir une taille connue à la compilation.
Nous arrivons maintenant dans le cœur nucléaire de l'opération. Grâce à l'opérateur ellipse, nous allons dérouler la boucle :
2.
3.
4.
template <typename T, long unsigned int N, long unsigned int... BRIndexes>
void bubble_sort_impl(std::array<T, N>& input_array, Index_vector<BRIndexes...>&&) {
auto n = { swap_if_less(input_array, BRIndexes)... };
};
C'est tout ! Grâce à l'opérateur ellipse, l'expression sera développée comme la boucle d'un tri-bulle :
n = { swap_if_less(array, 0), swap_if_less(array, 1), swap_if_less(array, 2), swap_if_less(array, 3), … , swap_if_less(array, 0) } ;
Le type de n est std::initializer_list<int> : il récolte les 0 renvoyés par swap_if_less, dont nous n'avons que faire. Il était néanmoins nécessaire que la fonction swap_if_less renvoie un type et toujours le même, afin que le compilateur puisse déduire la construction de la liste d'initialisation.
On voit que la syntaxe de std::initializer_list se marie très bien avec la façon dont l'opérateur ellipse agit : développement du template variadique en séparant ses éléments par des virgules.
Si cette variable inutile vous déplaît et vous semble bien inefficace, songez pourtant qu'elle disparaîtra à la compilation, pour peu que vous choisissiez un niveau d'optimisation suffisant.
Il nous reste à envelopper tout ça pour que la fonction soit plus agréable à utiliser : pour l'instant il faut fournir la séquence d'entiers soi-même :
2.
3.
4.
template <typename T, long unsigned int N>
void bubble_sort(std::array<T, N>& array) {
bubble_sort_impl(array, typename Bubble_ranges<N-1>::type()); // on déduit la longueur du tableau
}
Pour en avoir fini tout à fait, il faut quand même prévoir le cas où N est trop élevé : dans ce cas, le tri-bulle est trop désavantagé pour que notre optimisation soit efficace. Nous avons recours à std::enable_if_t : si la condition qui est son argument template échoue, la compilation échoue ; sinon il retourne void (le type que enable_if_t retourne peut être paramétré). Nous donnons deux surcharges de la fonction : c'est celle qui ne comporte pas d'erreur à la compilation qui sera choisie.
2.
3.
4.
5.
6.
7.
8.
template <typename T, long unsigned int N>
std::enable_if_t<(33ul > N)> optimal_sort(std::array<T, N>& array) {
bubble_sort(array); // tri-bulle ultra rapide
}
template <typename T, long unsigned int N>
std::enable_if_t<(N > 32ul)> optimal_sort(std::array<T,N>& array) {
std::sort(std::begin(array), std::end(array)); // std::sort
}
III-D-2. La méthode C++14▲
La seule différence notable entre les deux versions est la méthode de construction de la séquence d'indices. Une fois de plus, elle est plus concise et plus évocatrice :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
// le cas d'arrêt, placé encore une fois en premier
template <std::size_t... Ns>
constexpr auto build_bubble_range(std::index_sequence<0> z, std::index_sequence<Ns...> ns) {
return join(ns, z);
}
//le cas général
template <std::size_t N, std::size_t... Ns>
constexpr auto build_bubble_range(std::index_sequence<N> n, std::index_sequence<Ns...> ns = std::index_sequence<>()) {
return build_bubble_range(--n, join(ns, build_range(n));
}