Les templates variadiques en C++

Voir aussi : code source - vidéo youtube - vidéo peertube

Les templates variadiques sont des templates qui peuvent recevoir un nombre variable de paramètres. On peut donc les voir comme l’équivalent des fonctions variadiques (comme la fonction printf) mais pour les templates. Ils permettent d’implémenter des structures de données complexes, comme par exemple des tuples, tout en profitant du système de typage du compilateur. Les templates variadiques utilisent généralement des fonctionnalités classiques en programmation fonctionnelle, comme la récursivité ou la réduction.

Compléments sur les templates

Les paramètres non-types

Les templates sont souvent utilisés pour écrire du code générique par rapport à un type. Par exemple, on peut ainsi écrire un template pour définir une fonction sur un int ou sur un double ou autre. Autre exemple, le template de classe vector permet de créer des tableaux de int ou de double ou autre.

vector<int> v1;  // v1 est un tableau d'entiers, de taille dynamique

Cependant, les templates peuvent également prendre des paramètres “non-types”, c’est-à-dire des paramètres qui ne représentent pas un type générique mais une valeur (d’un type prédéfini). Par exemple, le template de classe array prend en paramètre le type des éléments du tableau mais également le nombre d’éléments du tableau, c’est-à-dire un int.

array<int, 3> v2;  // v2 est un tableau de 3 entiers

Par exemple, la structure Constant suivante permet de représenter un entier non modifiable.

struct Constant {
    const int _value;    // valeur de l'entier
    Constant(int value) : _value(value) {}
    int getValue() const { return _value; }    // accès à la valeur de l'entier
};

int main() {

    Constant c1(1);
    cout << c1.getValue() << endl;

    Constant c2(2);
    cout << c2.getValue() << endl;

    return 0;
}

On peut également implémenter Constant par un template dont le paramètre est la valeur de l’entier à représenter. On peut même oublier complètement l’attribut _value car sa valeur est déjà connue, avec le paramètre du template.

template <int V>
struct Constant {
    Constant() = default;
    int getValue() const { return V; }    // ici la valeur de l'entier est connu
                                          // d'après le paramètre du template
};

int main() {

    Constant<1> c1;
    cout << c1.getValue() << endl;

    Constant<2> c2;
    cout << c2.getValue() << endl;

    return 0;
}

Run-time vs compile-time

Un des points essentiels des templates est qu’ils sont instanciés à la compilation (compile-time) et non à l’exécution (run-time). Ceci permet au compilateur de vérifier le typage et d’optimiser le code généré. En revanche,
les paramètres du template doivent être connus dès la compilation.

Par exemple avec la structure Constant précédente, la version template n’est utilisable que si on connait la valeur représentée dès la compilation. Si cette valeur est connue à l’exécution, par exemple lors d’une saisie clavier ou via les arguments de la ligne de commande, alors la version template n’est pas applicable et il faut utiliser la version run-time classique.

Les templates récursifs

Les templates peuvent réaliser de la récursivité. Prenons l’exemple très classique de la suite de Fibonacci. Avec une implémentation (naïve et inefficace) sous forme de fonction récursive, on aurait le code suivant.

int fibo(int n) {
    assert(n >= 0);
    return n <= 1 ? n : fibo(n-1) + fibo(n-2);  // fonction récursive naïve
}

int main() {
    cout << fibo(0) << endl;
    cout << fibo(1) << endl;
    cout << fibo(2) << endl;
    cout << fibo(3) << endl;
    cout << fibo(42) << endl;
    return 0;
}

On peut implémenter un code équivalent avec des templates. Pour cela, on définit un template de structure paramétré par un int (la position dans la suite de Fibonacci) et contenant un attribut value (la valeur dans la suite pour cette position). L’attribut est calculé à l’instanciation du template, en instanciant récursivement le même template mais pour une valeur de paramètre différente. Comme pour toute définition récursive, il faut, en plus des appels récursifs, définir les cas terminaux. Ici, on pré-instancie le template pour les valeurs 0 et 1 de son paramètre.

template <int N> struct Fibo {
    static const int value = Fibo<N-1>::value + Fibo<N-2>::value;
        // instanciations récursives du template
};

template<> struct Fibo<0> {
    static const int value = 0;
        // instance terminale pour le paramètre de valeur 0
};

template<> struct Fibo<1> {
    static const int value = 1;
        // instance terminale pour le paramètre de valeur 1
};

int main() {
    cout << Fibo<0>::value << endl;
    cout << Fibo<1>::value << endl;
    cout << Fibo<2>::value << endl;
    cout << Fibo<3>::value << endl;
    cout << Fibo<42>::value << endl;
    return 0;
}

Bien entendu, cette implémentation de la suite de Fibonacci n’est utilisable que pour des valeurs du paramètre connues à la compilation.

On remarquera cependant que :

Templates variadiques, exemple 1 (Adder)

On veut implémenter une structure Adder. Cette structure est initialisée en lui passant un tableau d’entiers, dont elle calcule et stocke la somme.

Version run-time

Dans une version classique “run-time”, on utiliserait une structure avec un attribut _result. Le tableau d’entier serait passé en paramètre du constructeur, qui calculerait la somme et la stockerait dans _result.

struct Adder {
    int _result;
    Adder(const vector<int> & values) {
        _result = accumulate(values.begin(), values.end(), 0, plus<int>());
            // le résultat est calculé lors de la construction de l'objet
    }
};

int main() {
    Adder a1({1});
    cout << a1._result << endl;
    Adder a3({1,2,3});
    cout << a3._result << endl;
    return 0;
}

Version templates variadiques, par recursion

Dans une version “compile-time”, on peut passer les entiers comme paramètres de template. Il suffit donc de définir un template de structure variadique. Cette structure contient un attribut _result qui est calculé récursivement en ajoutant à la valeur du premier paramètre l’attribut _result du template correspondant au reste des paramètres.

template<int ... XS> struct Adder;

template<int X> 
struct Adder<X> {
    static const int _result = X;
        // instance terminale : s'il n'y a qu'un paramètre, 
        // alors le résultat est la valeur de ce paramètre
};

template<int X, int ... XS> 
struct Adder<X, XS ...> {
    static const int _result = X + Adder<XS...>::_result;
        // instanciation récursive : le résultat est la somme
        // du premier paramètre et du résultat de l'instanciation sur
        // le reste des paramètres
};

int main() {
    Adder<1> a1;
    cout << a1._result << endl;
    Adder<1,2,3> a3;
    cout << a3._result << endl;
    cout << Adder<1,2,3>::_result << endl;
    return 0;
}

On notera que le paramètre variadique est noté sous la forme int ... XS. Le symbole ... est parfois appelé “ellipse”.

Version templates variadiques, par folding

Depuis la norme C++17, on peut utiliser des “fold expressions”, c’est-à-dire des calculs de réduction sur le paramètre variadique. Ceci permet généralement de simplifier signicativement le code.

template <int ... XS>
struct Adder {
    static const int _result = (0 + ... + XS);  // utilisation d'une "fold expr"
};

int main() {
    Adder<1> a1;
    cout << a1._result << endl;
    Adder<1,2,3> a3;
    cout << a3._result << endl;
    cout << Adder<1,2,3>::_result << endl;
    return 0;
}

On notera que tous les codes ne sont pas forcément implémentables sous forme de fold expressions et qu’il est donc parfois nécessaire d’utiliser une forme récursive.

Templates variadiques, exemple 2 (Tensor)

L’exemple précédent est très artificiel. L’exemple ci-dessous illustre une utilisation plus réaliste des templates variadiques. Il s’agit de définir des tableaux multi-dimensionnels de tailles statiques avec quelques fonctionnalités de base : remplir le tableau avec une valeur donnée, accéder à un élément dans le tableau, ajouter un tableau dans un autre, multiplier toutes les valeurs par une constantes… Les templates permettent ici de réaliser certains calculs et vérifications dès la compilation et donc d’optimiser l’exécution.

Version run-time

struct Tensor {

    vector<int> _dims;
    vector<double> _data;

    explicit Tensor(const vector<int> & dims) : _dims(dims) {
        int n = accumulate(_dims.begin(), _dims.end(), 1, multiplies<int>());
        _data.resize(n);
    }

    void fill(const double & v) {
        std::fill(_data.begin(), _data.end(), v);
    }

    int ind(const vector<int> & inds) const {
        assert(inds.size() == _dims.size());
        assert(inds[0]<_dims[0]);
        int k = inds[0];
        for (unsigned i=1; i<_dims.size(); i++) {
            assert(inds[i]<_dims[i]);
            k = k * _dims[i] + inds[i];
        }
        return k;
    }

    double & operator()(const vector<int> & is) {
        return _data[ind(is)];
    }

    const Tensor & operator+=(const Tensor & t) {
        assert(_data.size() == t._data.size());
        for (unsigned i=0; i<t._data.size(); i++)
            _data[i] +=  t._data[i];
        return *this;
    }

};

Tensor operator*(double k, const Tensor & t1) {
    Tensor t2(t1._dims);
    for (unsigned i=0; i<t1._data.size(); i++)
        t2._data[i] = k * t1._data[i];
    return t2;
}

#include <iostream>

int main() {

    Tensor t1({2,3,4});
    t1.fill(7.0);
    Tensor t2({2,3,4});
    t2.fill(3.0);
    Tensor t3 = 2.0 * t1;

    t1 += t2;
    cout << t1({1, 2, 3}) << endl;
    cout << t2({1, 2, 3}) << endl;
    cout << t3({1, 2, 3}) << endl;

    t1({1, 2, 3}) = 0.0;
    cout << t1({1, 2, 3}) << endl;

    Tensor t4({2});
    t4.fill(22.0);
    Tensor t5({2});
    t5.fill(20.0);
    t4 += t5; 
    Tensor t6 = 2.0 * t4;
    cout << t6({1}) << endl;

    t1 += t4;    // erreur détectée à l'exécution

    return 0;
}

Version template variadique

template <int ... XS>
struct Tensor {

    static const int _K = (1 * ... * XS);
    array<double, _K> _data;
    static const int _D = sizeof...(XS);
    static constexpr array<int, _D> _dims {XS...};

    static_assert(_D > 0);

    void fill(const double & v) {
        _data.fill(v);
    }

    int ind(const array<int, _D> & inds) const {
        assert(inds[0]<_dims[0]);
        int k = inds[0];
        for (int i=1; i<_D; i++) {
            assert(inds[i]<_dims[i]);
            k = k*_dims[i] + inds[i];
        }
        return k;
    }

    double & operator()(const array<int, _D> & inds) {
        return _data[ind(inds)];
    }

    const Tensor<XS...> & operator+=(const Tensor<XS...> & t) {
        transform(_data.begin(), _data.end(), t._data.begin(),
                _data.begin(), plus<double>());
        return *this;
    }
};

template <int ... XS>
const Tensor<XS...> operator*(double k, const Tensor<XS...> & t1) {
    Tensor<XS...> t2;
    for (int i=0; i<t1._K; i++)
        t2._data[i] = k * t1._data[i];
    return t2;
}

#include <iostream>

int main() {

    Tensor<2,3,4> t1;
    t1.fill(7.0);
    Tensor<2,3,4> t2;
    t2.fill(3.0);
    Tensor<2,3,4> t3 = 2.0 * t1;

    t1 += t2;
    cout << t1({1,2}) << endl;
    cout << t2({1,2,3}) << endl;
    cout << t3({1,2,3}) << endl;

    t1({1,2,3}) = 0.0;
    cout << t1({1,2,3}) << endl;

    Tensor<2> t4;
    t4.fill(22.0);
    Tensor<2> t5;
    t5.fill(20.0);
    t4 += t5; 
    Tensor<2> t6 = 2.0 * t4;
    cout << t6({1}) << endl;

    t1 += t4;    // erreur détectée à la compilation

    return 0;
}

Conclusion

Les templates C++ proposent des fonctionnalités assez avancées. Ils permettent d’implémenter des structures avec des paramètres arbitraires mais correctement typés comme les tuples ou des bibliothèques de meta-programmation évoluées comme Boost Hana.

Les templates sont un aspect assez avancé du C++, qu’il peut être utile de maitriser pour développer des bibliothèques évoluées. Mais pour de nombreux cas d’utilisation du C++, une connaissance beaucoup plus basique est généralement largement suffisante.