Ce texte repose sur quelques techniques peu connues de la plupart des gens au moment d'écrire ces lignes. Avant de procéder, je vous recommande de lire et de comprendre cette brève introduction à la métaprogrammation.
Itérer, de manière itérative à proprement dit ou en procédant par récursivité est une tâche essentielle à pratiquement tout programme qui puisse être considéré comme sérieux.
Certaines itérations peuvent être résolues de manière statique, donc à la compilation, ce qui réduit la quantité de calculs à faire lors de l'exécution d'un programme. Cet article examinera, graduellement, des techniques pour exprimer des constructions itératives statiques.
Imaginons un problème aussi simple qu'afficher les entiers de à , exclus, pour un positif. On parle évidemment ici d'une problème jouet, qui n'a probablement de sens que dans un contexte académique, mais qui nous permettra de mettre en place les bases des approches plus polyvalentes qui suivront.
Si la valeur de est connue à l'exécution, une forme répétitive ou récursive traditionnelle est la chose à faire, mais il peut arriver que la valeur de N soit une constante connue à la compilation. Dans un tel cas, il pourrait être avantageux de laisser le compilateur générer les appels sans avoir à supporter une surcharge associée aux variables de contrôle de la répétitive ou aux inévitables branchements qui résulteront d'une récursive ou d'une répétitive.
Un exemple de code reconnaissant cette situation est proposé ci-dessous.
| Affichage ascendant | Affichage descendant |
|---|---|
|
|
Remarquez sa structure :
Plus près d'une solution générale, l'approche suivante permet d'intégrer un foncteur à la répétitive, donnant ainsi une sorte de std::for_each() sur une séquence d'entiers. Cet exemple applique le foncteur sur chaque entier dans la plage en ordre croissant et est à peu près conforme aux usages en C++.
#include <ostream>
class Afficher {
std::ostream &os;
public:
Afficher(std::ostream &os) : os{os} {
}
template <class T>
void operator()(const T &val) {
os << val << ' ';
}
};
template <int N>
struct static_for {
template <class Op>
void operator()(Op oper) const {
static_for<N-1>{}(oper);
oper(N-1);
}
};
template <>
struct static_for<0> {
template <class Op>
void operator()(Op) const {
}
};
#include <iostream>
int main() {
using std::cout;
static_for<10>{}(Afficher{cout});
}Un exemple plus riche utilisant un foncteur différent et calculant la somme des entiers de la séquence suit. Remarquez que la répétitive est évaluée à la compilation (du Loop Unrolling statique) mais que l'opérateur () du foncteur sera, bien entendu, invoqué à l'exécution.
Comme dans le cas de l'algorithme std::for_each(), le static_for retourne l'opération appliquée sur la séquence, ce qui permet une expression simple comme celle affichant la valeur résultant du calcul de la somme des valeurs d'une séquence.
#include <ostream>
class Afficher {
std::ostream &os;
public :
Afficher(std::ostream &os) : os{os} {
}
template <class T>
void operator()(const T &val) {
os << val;
}
};
template <class T>
class Cumuler {
T cumul;
public :
Cumuler(const T &init) : cumul{init} {
}
void operator()(const T &val) {
cumul += val;
}
T valeur() const {
return cumul;
}
};
template <int Debut, int Fin>
struct static_for_impl {
template <class Op>
Op operator()(Op oper) {
oper(Debut);
return static_for_impl<Debut + 1, Fin>{}(oper);
}
};
template <int N>
struct static_for_impl<N, N> {
template <class Op>
Op operator()(Op oper) {
return oper;
}
};
template <int Debut, int Fin, class Op>
Op static_for(Op oper) {
return static_for_impl<Debut, Fin>{}(oper);
}
#include <iostream>
int main() {
using namespace std;
static_for<0,10>(Afficher{cout});
cout << endl << static_for<0,10>(Cumuler<int>{0}).valeur() << endl;
}Il est possible de définir un static_for sur les éléments d'un tableau, ce qui ajoute beaucoup de flexibilité au modèle, mais avec quelques restrictions :
On aurait, en effet, voulu exprimer les extrémités de la séquence sur laquelle opérer par une paire de T* (le début et la fin de la séquence) et la terminer quand le début et la fin seraient identiques, mais cette forme n'est pas supportée pour le moment.
Remarquez que la manoeuvre repose à la base sur l'écriture template<class T, T *ptr>, donc sur un type générique puis sur une adresse de ce type qui sera connue à la compilation. La borne supérieure de l'itération est exprimée sous forme d'un entier parce que l'arithmétique de pointeurs n'est pas, au moment d'écrire ces lignes, réalisée de manière statique (un irritant conceptuel, à mes yeux).
#include <ostream>
class Afficher {
std::ostream &os;
public :
Afficher(std::ostream &os) : os{os} {
}
template <class T>
void operator()(const T &val) {
os << val;
}
};
template <class T>
class Cumuler {
T cumul;
public :
Cumuler(const T &init) : cumul{init} {
}
void operator()(const T &val) {
cumul += val;
}
T valeur() const {
return cumul;
}
};
template <class T, T *pDebut, int N, class Op>
struct static_for_impl {
Op operator()(Op oper) {
static_for_impl<T, pDebut, N-1, Op>{}(oper);
oper(*(pDebut+N-1));
return oper;
}
};
template <class T, T *pDebut, class Op>
struct static_for_impl<T, pDebut, 0, Op> {
Op operator()(Op oper) {
return oper;
}
};
template <class T, T *pDebut, int N, class Op>
Op static_for(Op oper) {
return static_for_impl<T, pDebut, N, Op>{}(oper);
}
struct Test {
enum { NELEMS = 5 };
static const int tab[NELEMS];
};
const int Test::tab[] = { 1, 2, 3, 4, 5 };
#include <iostream>
int main() {
using namespace std;
static_for<const int, Test::tab, Test::NELEMS>(Afficher{cout});
cout << '\n'
<< static_for<const int, Test::tab, Test::NELEMS>(Cumuler<int>{0}).valeur()
<< endl;
}À partir de cet exemple, il devient possible de réaliser un certain nombre d'optimisations intéressantes sans nécessairement devoir sacrifier flexibilité ou élégance. N'oublions pas que l'injection d'une séquence de foncteurs et le inlining peuvent, pris ensembles, révéler au compilateur des possibilités d'optimisation nouvelles et transformer certaines boucles complexes en une constante statique ou en une expression mathématique simplifiée.
Ce qui suit est un peu costaud. il est préférable d'avoir lu au préalable sur les listes de types et sur l'injection de parents. La démarche proposée dans cette section s'apparente à la programmation orientée aspect (POA).
Un brillant étudiant de la cohorte 02 du diplôme de développement du jeu vidéo à l'Université de Sherbrooke, le très chic Stéphane Bourque, m'a lancé sur la piste de ce qui suit : est-il possible d'injecter, à la compilation, des opérations applicables sur les différents types d'une liste de types?
La réponse me semblait être oui. En jouant un peu avec la syntaxe, j'y suis arrivé pour un exemple jouet. Voici ce que cela donne (vous pourrez sûrement développer la technique pour en tirer profit dans des cas plus concrets) :
Le code suit.
| Injection à la pièce | Injection par lot |
|---|---|
|
|
Un ami lecteur, Troctsch (aussi connu sous le nom de Sébastien), m'a fait remarquer que le code d'injection statique de fonctionnalités ci-dessus ne fonctionne pas sous g++ (du moins avec la version qu'il a sous la main), alors qu'elle compile bien avec diverses versions de Visual Studio. Cependant, la version canonique de cette manoeuvre (l'idiome CRTP, bien connu) fonctionne quant à elle très bien sur les deux plateformes. Merci!
Sachant cela, j'ai fait quelques tests et effectivement, ce ne sont pas tous les compilateurs qui considèrent cette manoeuvre comme étant légale. J'ai entre autres essayé le compilateur en-ligne de Comeau Computing et celui-ci, devant le code suivant :
class X {
friend int f(int n) {
return n + 1; }
}
};
template <class T>
void unused(T&&) {
}
int main() {
X x;
f(3);
}...produit un message d'erreur à l'effet que f n'est pas défini.
Je suis donc allé consulter le standard, soit §11.3 de http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3290.pdf (la plus récente version de C++ 11 en ma possession), et §11.4 de http://www-d0.fnal.gov/~dladams/cxx_standard.pdf (la plus récente version de C++ 98 à laquelle j'ai accès) et dans les deux cas, il me semble clair que ce code soit légal – en fait, le standard propose explicitement l'exemple suivant, et le qualifie de légal :
class M {
friend void f() {}
};...or, avec ces compilateurs, le programme suivant, correct selon le standard :
class M {
friend void f() {}
};
int main() {
f();
}...ne compile pas, qu'on déclare ou non une instance de M dans le programme. Par contre, l'idiome CRTP semble supporté de manière universelle. Ainsi, à ma connaissance du moins ceci :
template <class P>
class M {
friend void f(P) {
}
};
class X : M<X> {
};
int main() {
X x;
f(x);
}...compilera partout.
Nous conviendrons qu'un truc légal mais qui n'est pas supporté par notre compilateur de prédilection est d'une utilité mitigée. Mieux vaut le savoir avant de s'investir pleinement dans cette technique.
