static_accumulate – exemple

Le code présenté ici fonctionne avec C++ 03, mais il est possible de faire bien mieux depuis C++ 11. Pour un exemple plus à jour, voir static_exemples.html ou encore un peu plus bas sur la présente page

La métaprogrammation en C++ peut être difficile à aborder. On est en mesure de se demander à quoi cela peut servir, ou comment la mettre en pratique.

Pour en montrer une application concrète, nous implanterons ici une version statique d'un algorithme évaluant la somme des éléments d'une liste d'entiers. Nous enrichirons le tout pour en arriver à une version similaire à une implémentation statique d'un algorithme tel que std::accumulate() de la STL.

Nous utiliserons une version allégée (!) des listes de types d'Andrei Alexandescu, au sens où seul le fait qu'une telle liste comprenne une tête et une queue nous suffira (nous n'utiliserons que sa signature, pas ses types internes).

 
template <class, class>
   struct type_list {
   };
class Vide {};

Nous utiliserons une manoeuvre proposée entre autres par Dave Abrahams pour « convertir » des entiers connus à la compilation en types, sur une base individuelle. Ce faisant, nous pourrons raisonner à la compilation sur les valeurs ainsi représentées. 

template <int N>
   struct int_ {
      enum { value = N };
   };

L'évaluation statique de la somme des éléments d'une liste de types (de int_<N> pour divers entiers N, ici) se fait de manière récursive.

L'implémentation proposée ici est relativement simple. L'effort sera surtout porté sur la généralisation de cette solution pour couvrir d'autres types de cumuls qu'une simple somme. 

template <class>
   struct static_somme;
template <class T, class Q>
   struct static_somme<type_list<T,Q>> {
      enum { value = T::value + static_somme<Q>::value };
   };
template <>
   struct static_somme<Vide> {
      enum { value = 0 };
   };

En effet, pour un algorithme statique de cumul général, nous devrons utiliser une sorte de foncteur statique.

Ce foncteur (ici, F) suivra les usages de la fonction de cumul utilisée par std::accumulate(). Là où cette fonction est binaire (arité 2), notre foncteur sera un template sur la base de deux types, représentant la nouvelle valeur à cumuler et le cumul partiel.

Nous utiliserons des traits pour représenter la valeur initiale du cumul, soit 0 pour une somme et 1 pour un produit. Ces traits seront sur la base d'un foncteur statique à deux types, ce qui peut sembler inhabituel à première vue.

 
template <template <class, class> class>
   struct init_value_traits;

template <class, template <class, class> class>
   struct static_accumulate;
template <class T, class Q, template <class, class> class F>
   struct static_accumulate<type_list<T, Q>, F> {
      using type = typename
         F<T, typename static_accumulate<Q, F>::type>::type;
      enum { value = type::value };
   };
template <template <class, class> class F>
   struct static_accumulate<Vide, F> {
      using type = typename
         init_value_traits<F>::type;
      enum { value = type::value };
   };

Deux exemples de foncteurs statiques sont proposés à droite.

L'un réalise une somme statique à partir de deux types V (pour valeur courante) et CUMUL (pour valeur cumulée jusque là). L'autre fait de même pour un produit statique.

 
template <class V, class CUMUL>
   struct somme_statique {
      using type = int_<V::value + CUMUL::value>;
      enum { value = type::value };
   };
template <class V, class CUMUL>
   struct produit_statique {
      using type = int_<V::value * CUMUL::value>;
      enum { value = type::value };
   };

Tel que mentionné précédemment, les valeurs initiales pour chacun des foncteurs statiques sont exprimées sous forme de traits.

Visiblement, il est légal d'exprimer des traits pour des templates comme pour des classes.

 
template <>
   struct init_value_traits<somme_statique> {
      using type = int_<0>;
      enum { value = type::value };
   };
template <>
   struct init_value_traits<produit_statique> {
      using type = int_<1>;
      enum { value = type::value };
   };

Enfin, un programme de test montre comment il est possible d'utiliser tous ces outils. Il serait évidemment plus élégant d'utiliser des macros pour alléger l'écriture de la définition de la liste de types.

 
#include <iostream>
int main() {
   using namespace std;
   using vals = type_list<
      int_<2>, type_list<
         int_<3>, type_list<
            int_<5>, type_list<
               int_<7>, type_list<
                  int_<11>, Vide
               >
            >
         >
      >
   >;
   cout << static_somme<vals>::value << endl;
   cout << static_accumulate<vals,somme_statique>::value << endl;
   cout << static_accumulate<vals,produit_statique>::value << endl;
}

Et voilà.

Version C++ 11 (plus jolie, plus simple)

La version qui suit est présentée sans explications, les idées étant à peu près les mêmes que celles exposées ci-dessus, mais est écrite à l'aide de templates variadiques ce qui la rend plus concise et plus efficace en temps de compilation.

#include <iostream>
#include <tuple>
using namespace std;
template <class ... Ts>
   using type_list = tuple<Ts...>; // ou encore template <class...> struct type_list;

template <int N>
   struct int_ {
      enum { value = N };
   };

//
// Version de base (non-paramétrique; moins flexible), pour exposition seulement
//
// template <class> struct static_somme;
// template <class T, class ... Q> struct static_somme<type_list<T, Q...>> {
//    enum { value = T::value + static_somme<type_list<Q...>>::value };
// };
// template <> struct static_somme<type_list<>> {
//    enum { value = 0 };
// };

//
// Métafoncteurs
//
template <class T, class U> struct somme
: int_<T::value + U::value> {
};
template <class T, class U> struct produit
: int_<T::value * U::value> {
};

//
// Version paramétrique (plus flexible)
//
template <class TL, class INIT, template<class, class> class F>
   struct static_accumulate;
template <class T, class ... Q, class INIT, template<class, class> class F>
   struct static_accumulate <type_list<T, Q...>, INIT, F>
      : int_<F<
           T, typename static_accumulate<type_list<Q...>, INIT, F>
        >::value> {
   };
template <class T, class INIT, template<class, class> class F>
   struct static_accumulate <type_list<T>, INIT, F>
      : int_<F<T, INIT>::value> {
   };

int main() {
   using prems = type_list<int_<2>, int_<3>, int_<5>, int_<7>, int_<11>>;
   cout << static_accumulate<prems, int_<0>, somme>::value << endl;
   cout << static_accumulate<prems, int_<1>, produit>::value << endl;
}

Voilà!

Valid XHTML 1.0 Transitional

CSS Valide !