LES TEMPLATES VARIADIQUES, UN NOUVEL OUTIL DE PROGRAMMATION GÉNÉRIQUE

Stendhal666

Les templates variadiques en long, en large et en travers : tout ce que vous avez toujours voulu savoir sans jamais oser le demander !

Vous pouvez donner votre avis sur cet article sur le forum C++ : Commentez .

- Titre : LES TEMPLATES VARIADIQUES, UN NOUVEL OUTIL DE PROGRAMMATION GÉNÉRIQUE

- Auteur : Stendhal666

- Parution : 24 mai 2016

- Public visé :

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2016 Stendhal. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Qu'est-ce qu'un template variadique ?

- II-A. Une généralisation de la programmation générique en C++

- II-B. L'utilisation des templates variadiques dans la bibliothèque standard

- II-C. Le transfert parfait, ou perfect forwarding

- 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

- III-B. Vérifier l'adhésion des paramètres template à un concept : assertion statique et opérateur de fonction

- III-C. Générer des séquences d'entiers à la compilation

- III-C-1. La méthode de récursion par héritage

- III-C-2. La méthode C++14 : auto et fonctions constexpr

- III-C-3. Un exemple d'utilisation

- III-C-4. Fusionner deux ranges

- III-D. Optimiser le code : dérouler les boucles à la compilation pour un tri optimal

- III-D-1. La méthode C++11

- III-D-2. La méthode C++14

- IV. Conclusion

- V. Remerciements

I - Introduction

Le C++ a été l'un des premiers langages à offrir un support pour la programmation générique, grâce à l'introduction des templates. C'est ce qui a déterminé Alexander Stepanov, le père de la programmation générique, à écrire la standard template library (STL), qui constitue encore aujourd'hui l'essentiel de la bibliothèque standard du C++ et l'exemple le plus achevé de généricité.

Cet article n'a pas pour but de présenter la programmation générique. Pour ceux qui souhaiteraient s'initier ou approfondir la question, je conseille la lecture d'une interview d'Alexander Stepanov qui en présente les concepts et les perspectives. L'idée maîtresse est de ne pas programmer pour des types (int, float, MaClasse, MonInterface), mais pour des propriétés de type, ou concepts, afin de proposer des algorithmes et des conteneurs qui soient à la fois efficaces et généraux.

Le C++ est resté le refuge de la programmation générique quand la plupart des langages des années 1990-2000 ont choisi de rester dans les frontières de l'orienté objet. Des programmeurs de génie, comme Andrei Alexandrescu, ont repoussé les limites de ce qui paraissait possible avec la syntaxe du langage : les techniques qu'ils employaient étaient cependant si pointues qu'elles étaient de fait réservées à une petite minorité de programmeurs. Les Typelists dont Alexei Alexandrescu explique l'implémentation dans Modern C++ design sont ainsi les ancêtres des templates variadiques.

Le nouveau standard du C++ (C++11/14) a cherché à améliorer encore le support du langage pour la généricité, afin de rendre l'accès à certaines possibilités beaucoup plus large. Les templates variadiques font partie de ces nouveautés. Cet article cherche à les présenter en profondeur, de leur syntaxe à des utilisations avancées.

II - Qu'est-ce qu'un template variadique ?

II-A - Une généralisation de la programmation générique en C++

Un template variadique permet de paramétrer par un nombre indéterminé de types une classe, une fonction ou une directive (par exemple, la directive using).

printf sur fond de template variadique

1. // notre fonction printf prend une chaîne de caractères et un nombre indéterminé d'arguments (0 - +∞)

2. template <typename... T> void printf(const char* format, T... args) ;

Contrairement aux fonctions et aux macros variadiques du C, dont la fonction standard printf est l'exemple le plus célèbre, le nombre et le type des arguments d'un template variadique peuvent être vérifiés. C'est un des objectifs de leur introduction : améliorer la sécurité du code par rapport à ces anciennes fonctionnalités. Mais les templates variadiques ont d'autres supériorités sur les constructions variadiques du C :

- l'argument précédant l'ellipse dans une fonction C est nécessairement un type POD (pour plain old data, plus de précisions ici), ce qui exclut l'utilisation d'une std::string, pourtant bien pratique pour des fonctions de log, par exemple ;

- l'ellipse d'une construction variadique du C doit nécessairement être précédée d'un argument de type déterminé : elle ne permet donc pas des constructions aussi génériques que le template variadique, qui représente aussi bien aucun type qu'une infinité de types (dans la limite des capacités de traitement du compilateur).

Les types recouverts par le template variadique forment un parameter pack. Un parameter pack est introduit par l'opérateur ellipse (…). En voici quelques exemples :

Exemples de parameter packs

1. template <typename... Types> struct Some_types {} ; // Types est un parameter pack

2. Some_types<char, int, long, long long> entiers ; // il contient ici char, int, long, long long

3. template <int... ints> struct Ints ; // un parameter pack peut aussi contenir des constantes

Dans les paramètres templates d'une déclaration de classe, il ne peut y avoir qu'un parameter pack et il doit être le dernier des paramètres templates.

Cette restriction ne vaut pas pour les spécialisations de templates ni pour les fonctions.

Naturellement, le pack peut être développé pour retrouver les types qu'il contient. Cette étape s'appelle pack expansion. Cette opération est également réalisée grâce à l'opérateur ellipse, placé cette fois après le parameter pack. Regardez à nouveau la signature de printf pour voir un premier exemple :

la signature de printf

1. template <typename... T>

2. void printf(const char* format, T... args) ;

L'opérateur ellipse développe l'argument T en t1, t2, … tn. Il n'est pas nécessairement placé directement après le parameter pack : celui-ci peut être compris dans une expression, de complexité arbitraire, qui sera développée en même temps que lui. Voici un exemple -pas très utile- avec une structure qui affiche les valeurs par défaut des types qui la paramètrent :

Développer une expression complexe

1. template <typename... Types>

2. struct Default_values {

3. void affiche() {

4. auto n = { (std::cout << Types{} << ' ', 1)... };

5. }

6. };

Nous reviendrons sur cette technique un peu étonnante plus tard, je voulais juste montrer qu'une expression compliquée pouvait être développée lors de la pack expansion.

L'ellipse se retrouve encore dans l'opérateur sizeof... qui permet de connaître le nombre de types contenus dans le parameter pack. Par exemple :

sizeof...

1. template <typename... Types>

2. struct Arg_counter { static constexpr std::size_t value = sizeof...(Types) ; } ;

Regardons maintenant un peu quel parti les auteurs de la bibliothèque standard en ont tiré.

II-B - L'utilisation des templates variadiques dans la bibliothèque standard

template <typename... T> std::tuple: les tuples sont des généralisations de la paire. Au lieu d'être limités à deux éléments, ils peuvent en contenir un nombre arbitraire.

Un tuple de paramètres

1. std::tuple<std::size_t, std::size_t, float, float> algo_params ;

Les tuples sont dotés d'un opérateur de comparaison lexicographique : ses éléments sont comparés dans l'ordre, comme lorsque l'on compare deux chaînes de caractères. Ils sont fréquemment utilisés pour en bénéficier. La fonction std::tie crée un tuple de références à ses arguments  :

un tuple comparateur

1. struct Date {

2. int day, month, year ;

3. bool operator<(const Date& o) {

4. return std::tie(year, month, day) < std::tie(o.year, o.month, o.day) ;

5. }

6. } ;

On accède aux membres du tuple grâce à la fonction get :

l'accesseur

1. std::get<0>(mon_tuple) ; // renvoie le premier élément

template <class ReturnTypes, class... Args> std::function: ce foncteur générique universel permet d'envelopper n'importe quelle fonction, qu'elle appartienne ou non à une classe, foncteur ou lambda. Il peut être très utile pour conserver des fonctions « call-back » dans une classe qui les appellera plus tard, par exemple.

Une observation : il n'existe pas de fonction std::make_function qui déduise le type d'une fonction donnée en argument pour créer un foncteur universel, parce que des ambiguïtés sont possibles dès lors que la fonction est surchargée. Si le std::thread peut déduire le type de la fonction, c'est qu'il dispose aussi du type de ses arguments.

template <class Fn, class... Args> thread(Fn&&, Args&&...): le constructeur de thread prend en paramètre une fonction Fn (sous la forme d'un pointeur sur fonction, d'un pointeur sur une fonction membre, ou de tout foncteur ou fonction lambda) et ses arguments Args... pour créer un nouveau thread.

Si l'on compare avec l'implémentation des threads en C, par exemple avec pthread, on voit l'avantage : il n'est plus besoin d'effacer les types ou le nombre d'arguments de la fonction lancée dans le thread, derrière une signature comme (void*)(*threaded_function)(void* argument_structure). Comparez :

C thread

1. typedef struct Result { /* le résultat de la fonction */} Result ;

2. Result* my_function(int, double, char) ;

3. // qu'il faut traduire en :

4. typedef struct Arguments { int i, double d, char c } ;

5. Arguments args = {1, 2.5, 'f' } ;

6. void* thread_thread_signature(void* idc) {

7. Arguments* args = idc ;

8. return my_function(args->i, args->d, args->c) ;

9. }

10. // enfin !

11. int t = pthread_create(… , &thread_signature, &args) ;

12. // et il faudra caster la valeur de retour

et

c++ thread

1. std::thread t(&my_function, 1, 2.5, 'f') ;

Le gain en sécurité se double d'un gain en performance, qui vient de ce qu'il n'est plus nécessaire de « traduire » les arguments ou le type de retour.

Les plus attentifs d'entre vous auront remarqué la signature étrange du constructeur de thread : template <class Fn, class... Args> thread(Fn&&, Args&&...). Cet idiome -des arguments template sous forme de rvalue reference- permet ce qui est appelé perfect forwarding, ou en français, transfert parfait. C'est une des possibilités les plus intéressantes ouvertes par les templates variadiques.

II-C - Le transfert parfait, ou perfect forwarding

Le transfert parfait ne modifie pas le type des arguments transférés. Si on reçoit une lvalue, on retourne une lvalue, pareil pour une rvalue (si vous voulez rafraîchir votre mémoire sur le sujet des lvalues et rvalue, vous pouvez regarder ici). Ce qui pouvait sembler un détail dans les versions précédentes du standard est devenu capital désormais, car les opérations portant sur une rvalue peuvent être bien plus rapides que leur équivalent lvalue : c'est tout le sujet de la move semantic qui est un des apports majeurs des derniers standards.

Un argument template comme T&& ressemble à une rvalue, mais ne l'est pas vraiment ; c'est plutôt une opération de type : "au type initial représenté par T on ajoute &&". Par exemple, si le type initial est Ma_classe&, on obtient Ma_classe&&&. Ce qui n'existe pas. Les règles du C++ exigent que les esperluettes au-delà de deux soient contractées selon les règles suivantes :

- &&& => &

- &&&& => &&

Donc Ma_classe& && équivaut à MaClasse&, soit une lvalue reference. De même, Ma_classe&& && donne Ma_classe&&, soit une rvalue reference. C'est pour cette raison que l'on appelle les références templates de type T&& des références universelles. Elles constituent la première pierre du transfert parfait.

Cela ne suffit pas toujours :

Mauvais transfert

1. template <typename Fn, typename... Args>

2. thread(Fn&& fn, Args&&... args) {

3. // …

4. fn(args...) // args a un nom, une adresse → c'est une lvalue !

5. // …

6. }

Pour faire les choses bien, il faut faire dans le corps de la fonction ce que la référence universelle a fait aux arguments. C'est le rôle de la fonction standard std::forward, qui a exactement le même effet.

transfert parfait

1. template <typename Fn, typename... Args>

2. thread(Fn&& fn, Args&&... args) {

3. // …

4. fn(std::forward<Args>(args)...) // args garde son type originel

5. // …

6. }

Cette technique a un emploi qu'il faut connaître dans la bibliothèque standard. Les conteneurs ont désormais, à côté de la fonction push_back ou insert, une fonction emplace_back ou emplace qui utilise le perfect forwarding.On passe à emplace_back les arguments pour un des constructeurs du type contenu, et il crée l'objet directement dans la mémoire allouée. Il n'est donc plus nécessaire de créer une copie de l'objet pour l'insérer dans le conteneur, ni même de le transférer (pour le cas où la move semantic est prévue). S'il avait fallu copier les arguments du constructeur, le gain aurait été faible ; mais grâce à la combinaison entre les templates variadiques, qui permettent de cibler n'importe quel constructeur et les références universelles, qui permettent de conserver le type exact des arguments, une construction directe dans la mémoire allouée est possible.

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.

le cas de base

1. void printf(const char* format) { // cas de base : il n'y a qu'une chaîne de format

2. while (*format) {

3. if (*format == '%' && *++format != '%') // %% == % (pas une directive)

4. throw std::invalid_argument("Pas assez d'arguments !\n");

5. std::cout << *format++;

6. }

7. }

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 :

le cas général

1. template <typename Arg, typename... Args>

2. void printf(const char* format, Arg arg, Args... args) {

3. while (*format) {

4. if (*format == '%' && *++format != '%') {

5. std::cout << arg; // déduit tout seul le type d'argument

6. return printf(++format, args...); // la récursion, arg en moins

7. }

8. std::cout << *format++;

9. } // on a fini la chaîne de format et il nous reste des arguments : throw

10. throw std::invalid_argument("Too many arguments for printf\n");

11. }

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 :

vérification des types

1. template <typename Arg, typename... Args>

2. void printf(const char* format, Arg arg, Args… args) {

3. …

4. switch(current_format_qualifier) {

5. case 'd' : if ( ! is_integral<Arg>() ) throw std::invalid_argument() ;

6. …

7. }

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 :

vérfier si c'est un entier

1. #include <type_traits>

3. template <typename Integer>

4. Integer modulo(Integer a, Integer b) {

5. static_assert(std::is_integral<Integer>::value, " Integer doit être un type entier ! ") ;

6. …

7. }

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 :

Est-ce un foncteur?

1. template <typename T, typename... Args>

2. 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 :

une ellipse différente...

1. constexpr auto _has_func_operator(...) { // c'est la signature la moins déterminée

2. return false; // donc la moins attirante

3. }

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 :

Lorsqu'il y a bien un opérateur de fonction

1. template <typename Type, typename... Args>

2. constexpr auto _has_func_operator(int)

3. -> decltype(std::declval<Type>()(std::declval<Args>()...), bool()) {

4. return true;

5. }

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 :

pack développé

1. 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 :

Interface de trait

1. template <typename Type, typename... Args>

2. struct is_functor{

3. static constexpr bool value = _has_func_operator<Type, Args...>(0);

4. };

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 :

fin de la récursion

1. template <long unsigned int... Ns> // voilà nos entiers

2. struct Index_vector {

3. using type = Index_vector<Ns...>; // l'utilité de cet alias apparaîtra plus tard...

4. };

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 :

push front

1. template <typename Index_vector, long unsigned int N>

2. struct Push_front; // la signature à spécialiser

4. template <long unsigned int... Ns, long unsigned int N> // la spécialisation

5. 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 :

l'utilité de l'alias

1. using deux_trois = Index_vector<2,3> ;

2. using un_deux_trois = Push_front<deux_trois, 1> ;

3. // 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.

fin de la séquence

1. // Le terme à ajouter est 0, c'est la fin de la séquence

2. template <typename Index_vector>

3. struct Range<0, Index_vector> : Push_front<Index_vector, 0>::type {};

Et maintenant le cas général :

le cas général

1. // !! le deuxième paramètre est par défaut un Index_vector vide

2. template <long unsigned int rangesz, typename Index_vector = Index_vector<> >

3. struct Range : Range<rangesz-1, typename Push_front<Index_vector, rangesz>::type > {};

Essayons de démêler un peu tout ça :

c'estplus clair ?

1. Range<5> r5 ; // <=> Range<5, Index_vector<>> grâce au template par défaut

2. // hérite de :

3. Range<5-1, typename Push_front<Index_vector<>, 5>> //qui

4. // hérite de

5. Range<4-1, typename Push_front<Index_vector<5>, 4>> // qui

6. //hérite de

7. Range<3-1, typename Push_front<Index_vector<4,5>, 3>>

8. // …

9. // hérite de :

10. Range<0, typename Push_front<5,4,3,2>, 1>>

11. // hérite de (cas d'arrêt) :

12. Push_front<Index_vector<5,4,3,2,1>, 0>

13. // 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:

Commparaison 11/14

1. // C++11

2. auto func(int i) -> decltype(i) {

3. return i ;

4. }

5. // C++14

6. auto func(int i) {

7. return i ;

8. }

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 :

std::index_sequence

1. Namespace std {

2. template <std::size_t... Ns>

3. struct index_sequence {} ;

4. }

Commençons par une courte fonction constexpr qui décrémente une index_sequence composée d'un seul nombre :

Décrémentation

1. template <std::size_t N>

2. constexpr auto operator--(std::index_sequence<N>) {

3. return std::index_sequence<N-1>();

4. }

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 :

build_range

1. // 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

2. template <std::size_t... Ns>

3. constexpr auto build_range(std::index_sequence<0>, std::index_sequence<Ns...>) {

4. return std::index_sequence<0, Ns...>();

5. }

7. // le cas général : remarquez l'utilisation de l'opérateur de décrémentation défini dans l'exemple précédent

8. template <std::size_t N, std::size_t... Ns>

9. constexpr auto build_range(std::index_sequence<N> n, std::index_sequence<Ns...>) {

10. return  build_range_impl(--n, std::index_sequence<N, Ns...>());

11. }

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 :

appeler une fonction avec un tuple

1. template <typename Fn, typename... Args, std::size_t... Idx>

2. decltype(auto) call_with_tuple_impl(Fn fn, const std::tuple<Args...>& targs, Index_vector<Idx...>&&) {

3. return fn(std::get<Idx>(targs)...);

4. }

6. template <typename Fn, typename... Args>

7. decltype(auto) call_with_tuple(Fn fn, const std::tuple<Args...>& targs)

8. {

9. return call_with_tuple_impl(fn, targs, Range<sizeof...(Args)-1>());

10. }

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 :

à jamais dans les limbes

1. template <typename IV1, typename IV2>

2. 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 :

dans le ventre des séquences

1. template <long unsigned int... lhs, long unsigned int... rhs>

2. 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 :

join 14

1. template <std::size_t... Ms, std::size_t... Ns>

2. constexpr auto join(const std::index_sequence<Ms...>, std::index_sequence<Ns...>) {

3. return std::index_sequence<Ms..., Ns...>();

4. }

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 :

tri-bulle vanilla

1. // tri bulle sans fioritures

2. for (int i = tabsize-1 ; i ≥ 0 ; --i) {

3. for (int j = 0 ; j < i ; ++j) {

4. if (tab[j+1] < tab[j]) std::swap(tab[j], tab[j+1]) ;

5. }

6. }

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

le générateur d'indices

1. // le cas d'arrêt : on est arrivés à 0

2. template <>

3. struct Bubble_ranges<0> : Range<0> {};

5. // le cas général : on joint par récursion-héritage une séquence N avec une BubbleRange N-1

6. template <long unsigned int N>

7. 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 :

le générateur à l'œuvre

1. Bubble_ranges<4> ; // qui hérite de

2. Join_ranges<typename Range<4>::type, typename Bubble_ranges<4-1>::type>

3. // <=> Join_ranges<Index_vector<0,1,2,3,4>, typename Bubble_ranges<3>::type>

4. // or Bubble_ranges<3> hérite de

5. Join_ranges<Index_vector<0,1,2,3>, typename Bubble_range<2>::type>

6. // …

7. Bubble_ranges<O> ; // qui hérite de Range<0>, soit IndexVector<0>

8. // on pourrait aussi exprimer ce développement comme :

9. 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 :

la fonction de comparaison et d'échange

1. template <class T, long unsigned int N>

2. int swap_if_less(std::array<T, N>& array, const long unsigned int i) {

3. if (array[i+1] < array[i]) std::swap(array[i+1], array[i]);

4. return 0;

5. }

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 :

magie!

1. template <typename T, long unsigned int N, long unsigned int... BRIndexes>

2. void bubble_sort_impl(std::array<T, N>& input_array, Index_vector<BRIndexes...>&&) {

3. auto n = { swap_if_less(input_array, BRIndexes)... };

4. };

C'est tout ! Grâce à l'opérateur ellipse, l'expression sera développée comme la boucle d'un tri-bulle :

développement

1. 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 :

plus net (ou plus plus plus)

1. template <typename T, long unsigned int N>

2. void bubble_sort(std::array<T, N>& array) {

3. bubble_sort_impl(array, typename Bubble_ranges<N-1>::type()); // on déduit la longueur du tableau

4. }

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.

static dispatch

1. template <typename T, long unsigned int N>

2. std::enable_if_t<(33ul > N)> optimal_sort(std::array<T, N>& array) {

3. bubble_sort(array); // tri-bulle ultra rapide

4. }

5. template <typename T, long unsigned int N>

6. std::enable_if_t<(N > 32ul)> optimal_sort(std::array<T,N>& array) {

7. std::sort(std::begin(array), std::end(array)); // std::sort

8. }

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 :

bubble range 14

1. // le cas d'arrêt, placé encore une fois en premier

2. template <std::size_t... Ns>

3. constexpr auto build_bubble_range(std::index_sequence<0> z, std::index_sequence<Ns...> ns) {

4. return join(ns, z);

5. }

7. //le cas général

8. template <std::size_t N, std::size_t... Ns>

9. constexpr auto build_bubble_range(std::index_sequence<N> n, std::index_sequence<Ns...> ns = std::index_sequence<>()) {

10. return build_bubble_range(--n, join(ns, build_range(n));

11. }

IV - Conclusion

Je n'ai pas mesuré de façon très professionnelle le gain en temps d'exécution que permet notre tri-bulle. Avec l'optimisation au maximum (O3), en répétant l'essai une dizaine de fois, en alternant les deux méthodes de tri pour 200 000 tableaux de dix valeurs pour éviter les effets de cache, la version tri-bulle était entre 40 et 50 fois plus rapide que la version std::sort. Ce n'est certainement pas utile tous les jours, std::sort reste certainement le bon réflexe, mais si l'on a d'énormes quantités de tableaux à trier et que l'on connaît leur taille à l'avance…

Une conclusion plus générale, que je souhaiterais que vous puissiez tirer de cet article, est que les outils mis à la disposition du programmeur avec les nouveaux standards, petit à petit, lui permettent de tirer parti de toute la puissance du langage sans recourir à des tournures exagérément ésotériques. Il n'est plus nécessaire de s'appuyer sur une bibliothèque tierce pour aller au-delà des techniques les plus triviales de la méta-programmation. Il y a fort à parier que cette évolution se poursuive.

V - Remerciements

Je souhaite remercier toute l'équipe de Developpez.com, en particulier Francis Walter qui m'a encouragé à écrire mon premier article.

S'il est de qualité, ce sera grâce aux relectures techniques précises et documentées de Luc Hermitte, white_tentacle et Winjerome.

S'il est débarrassé de ses fautes de français, ce sera grâce aux relectures orthographiques attentives et patientes de Jacques_jean.

Merci !