Programmation C++ : CM séance 05

10. Templates

Un template (modèle, patron) est un mécanisme qui permet au programmeur d'utiliser des types comme paramètres pour des classes ou des fonctions.

On a déjà utilisé ce mécanisme avec des conteneurs pour spécifier le type des éléments, par exemple quand on déclare un vector :

std::vector<int>                    // un vector d'entiers
std::vector<MaClasse>               // un vector d'instances de MaClasse
std::vector<std::vector<double>>    // un vector de vectors de doubles

10.1. Fonction template

La syntaxe pour déclarer une fonction template est :

template <typename T, ....>        // typename ou class
TypeRésultat nom_fonction (TypeParamètre paramètre, ....)
{
    .... T ....                   // on utilise T comme un type normal
};

Le type T en argument est appelé un type générique. La première ligne signifie "pour tous les types génériques T".

Il peut y avoir plusieurs types génériques entre les <....>, par exemple

template <typename T, typename U>

Les types TypeRésultat ou TypeParamètre peuvent être des types normaux ou l'un des types génériques (T, U, ...) passés en paramètre dans la définition.

On peut ensuite appeler cette fonction comme une fonction normale, en écrivant :

nom_fonction (TypeParamètre paramètre, ....)

L'idée est que le compilateur va déduire les types effectifs à partir de la signature de la fonction (utilisation implicite du template). Pour que ça marche, il faut que tous les types génériques soient utilisés parmi les TypeParamètres.

Il est aussi possible de réaliser une utilisation explicite du template en donnant les types effectifs entre <....> dans l'appel :

nom_fonction<UnType, ....> (TypeParamètre paramètre, ....)

Dans les deux cas le compilateur génère alors tout le code de la fonction nom_fonction en remplaçant chaque type générique par le type effectif correspondant, ceci pour chaque signature de la fonction rencontrée dans le programme.

Exemple :

template <typename T>
T somme (T x, T y)
{
    return x+y;
}

int main()
{
    auto s1 = somme (3, 5);                 // int,int
    std::cout << s1 << std::endl;           // 8
    auto s2 = somme (5.1, 7.2);             // double,double
    std::cout << s2 << std::endl;           // 12.3
    auto s3 = somme (5.1, 4);               // erreur : conflit de types
    std::cout << s3 << std::endl;
    auto s4 = somme<double> (5.1, 4);       // utilisation explicite
    std::cout << s4 << std::endl;           // 9.1
}

Cette fonction sera utilisable pour tout type générique T pour lequel l'opérateur + est défini et dont le résultat est de type T. S'il y a un soucis il sera détecté à la compilation.

Surcharge

Une fonction template peut être surchargée ; en cas d'ambiguité c'est la fonction non template qui gagne :

template <typename T>
T somme (T x, T y)
{
    return x+y;
}

int somme (int x, int y)                    // cette fonction gagne
{
    std::cout << "trace1 ";
    return x+y;
}

int main()
{
    auto s1 = somme (3, 5);                 // int,int
    std::cout << s1 << std::endl;           // trace1 8
    auto s2 = somme (5.1, 7.2);             // double,double
    std::cout << s2 << std::endl;           // 12.3
    auto s3 = somme (5.1, 4);               // converti en int,int
    std::cout << s3 << std::endl;           // trace1 9
}

10.2. Classe template

La syntaxe pour déclarer une classe template est :

template <typename T, ....>        // typename ou class
class NomDuPatron {
    .... T ....                   // on utilise T comme un type normal
};

La première ligne signifie également "pour tous les types génériques T" ; il peut y en avoir plusieurs entre les <....>.

On peut ensuite instancier (explicitement) la classe template en écrivant :

NomDuPatron<UnType, ....> une_instance;

Le compilateur génère alors tout le code de la classe NomDuPatron en remplaçant chaque type générique par le type effectif correspondant, ceci pour chaque combinaison de types effectifs rencontrés dans le programme.

Exemple :

template <typename K, typename V>
class KeyValue {
private:
    K m_key;
    V m_value;
public:
    KeyValue (K key, V value) : m_key {key}, m_value {value} {}
    K key() const { return m_key; }             // getter
    void key (K key) { m_key = key; }           // setter
    V value() const { return m_value; }         // getter
    void value (V value) { m_value = value; }   // setter
    void show() { std::cout << m_key << " " << m_value << std::endl; }
};

int main()
{
    KeyValue a { "larg", 5 };       // KeyValue<const char*, int>
    a.show();                       //   larg 5
    KeyValue b { 7, true };         // KeyValue<int, bool>
    b.show();                       //   7 1
    auto c = a;                     // KeyValue<const char*, int>
    c.show();                       //   larg 5
    c.key("haut"); c.value(8);      // const char* ; int
    c.show();                       //   haut 8
    c.value("test");                // erreur, int attendu
}

Remarques :

• Les templates sont très efficaces car dupliqués à la compilation, il n'y a pas comme pour les classes virtuelles de VTBL à l'exécution.

• Les templates sont très puissants au niveau du langage, mais les erreurs à la compilation peuvent générer de très nombreux messages d'erreur.

• On peut définir un template avec un nombre de types génériques variable, cela s'appelle un template variadique (variadic template) avec l'opérateur ... ; C++17 apporte le mot réservé fold pour simplifier.

10.3. Classe de traits

Les templates sont également utiles pour définir des classes de traits.

Le mot "trait" signifie en anglais : caractéristique, propriété, et en français il apparaît dans l'expression "traits de caractère".

Une classe de traits est une classe qui permet de vérifier certaines caractéristiques à la compilation. Leur utilisation a été introduite par Nathan C. Myers en 1995.

Concrètement, une classe de traits est un simple classe template, pouvant contenir des données membre statiques, ou encore des typedef.

Voici un exemple de classe de traits qui détermine si un type est entier. On commence par écrire le cas général  :

template <typename T> 
struct is_integer
{
    static const bool value = false;
};

puis on le spécialise :

template <>
struct is_integer<int>
{
    static const bool value = true;
};

template <>
struct is_integer<char>
{
    static const bool value = true;
};

On peut ensuite utiliser la classe de traits is_integer de cette façon :

int main()
{
    std::cout << "Type char  : " << is_integer<char>::value  << "\n"    // 1
              << "Type float : " << is_integer<float>::value << "\n"    // 0
              << "Type int[] : " << is_integer<int[]>::value << "\n";   // 0
}

ou pour définir d'autres templates :

template <typename T>
void do_something (T a)
{
    if (!is_integer<T>::value) {
        std::cerr << "Error in do_something: integer expected\n";
        return;
    }
    std::cout << "do_something: " << a << "\n";
}

int main()
{
    do_something (25);      // do_something: 25
    do_something ('A');     // do_something: A
    do_something (3.14);    // Error in do_something: integer expected
}

De nombreuses classes de traits sont prédéfinies dans la STL.

Remarque : le C++20 a introduit les concepts, qui sont des ensembles nommés de contraintes sur les templates (mots réservés constraint, requires). Un des objectifs est d'avoir des messages d'erreurs plus clairs et concis. Mais ils ne remplacent pas les classes de traits, et les deux peuvent être combinés.

11. Surcharge des opérateurs

La plupart des opérateurs du C++ (+, ==, etc) peuvent être surchargés, c'est-à-dire redéfinis, pour agir sur certains types.

La syntaxe de la déclaration est similaire à celle d'une fonction :

TypeRésultat operator@ (TypeParamètre paramètre, ....) { /* corps */ }

où @ est l'opérateur à surcharger, par exemple +, *, ==, [], etc.

Les opérateurs peuvent être surchargés par une fonction membre (dans une classe) ou fonction non-membre (fonction ordinaire).

11.1. Par fonction membre

Elle permet de définir un opérateur @ sur une instance a d'une classe, avec un paramètre éventuel b de type quelconque :

• @a est surchargé par : a.operator@ () ;
• a@b est surchargé par : a.operator@ (b) ;
• autres cas plus loin.

Exemple : surcharge de == et != :

class Fraction {
private:
    int m_p, m_q;
public:
    Fraction (int p, int q) : m_p {p}, m_q {q} {}
    bool operator== (const Fraction& other) {
        return m_p == other.m_p && m_q == other.m_q;
    }
    bool operator!= (const Fraction& other) {
        return !(*this == other);               // on réutilise ==
    }
};

int main()
{
    Fraction a {3, 5};
    Fraction b {4, 7};
    std::cout << (a == a) << " "            // 1
              << (a != a) << " "            // 0
              << (a == b) << " "            // 0
              << (a != b) << std::endl;     // 1
}

Surcharge de la multiplication * avec création d'une Fraction :

class Fraction {
private:
    int m_p, m_q;
public:
    Fraction (int p, int q) : m_p {p}, m_q {q} {}
    void show() { std::cout << m_p << "/" << m_q << std::endl; }
    Fraction operator* (const Fraction& other) {
        int p = m_p * other.m_p;
        int q = m_q * other.m_q;
        return Fraction {p, q};
    }
};

int main()
{
    Fraction a {3, 5};
    Fraction b {4, 7};
    Fraction c = a*b;
    c.show();                   // 12/35
}

La surcharge peut aussi être déclarée forward (utile pour la modularité) :

class Fraction {
private:
    int m_p, m_q;
public:
    Fraction (int p, int q) : m_p {p}, m_q {q} {}
    void show() { std::cout << m_p << "/" << m_q << std::endl; }
    Fraction operator+ (const Fraction& other);
};

Fraction Fraction::operator+ (const Fraction& other) {
    int p = m_p*other.m_q + m_q*other.m_p;
    int q = m_q*other.m_q;
    return Fraction {p, q};
}

int main()
{
    Fraction a {3, 5};
    Fraction b {4, 7};
    Fraction d = a+b;
    d.show();                   // 41/35
}

11.2. Par fonction non membre

Les surcharges de certains opérateurs peuvent encore être déclarés comme des fonctions ordinaires (non-membre) ; dans ce cas, l'opérateur @ prend un objet en premier paramètre (et on aura besoin de getters) :

• @a est surchargé par : operator@ (a) ;
• a@b est surchargé par : operator@ (a, b) ;

class Fraction {
private:
    int m_p, m_q;
public:
    Fraction (int p, int q) : m_p {p}, m_q {q} {}
    int p() const { return m_p; }       // getter
    int q() const { return m_q; }       // getter
    void show() { std::cout << m_p << "/" << m_q << std::endl; }
};

Fraction operator/ (const Fraction& left, const Fraction& right)
{
    int p = left.p() * right.q();
    int q = left.q() * right.p();
    return Fraction {p, q};
}

int main()
{
    Fraction a {3, 5};
    Fraction b {4, 7};
    Fraction e = a/b;
    e.show();                   // 21/20
}

La surcharge des opérateurs dans des fonctions ordinaires est intéressante quand l'opération concerne des objets différents (exemple : Matrice * Vecteur). On peut éviter l'emploi de getters en déclarant la fonction amie (friend) dans les classes concernées.

11.3. Opérateurs de flux

La surcharge des opérateurs de flux << et >> (stream operators) ne peux être faite que via des fonctions non membre :

• l'opérateur << prend en paramètre le flux de sortie de type std::ostream (pour output stream) et l'objet, puis renvoie le flux ;
• l'opérateur >> prend en paramètre le flux d'entrée de type std::istream (pour input stream) et l'objet, puis renvoie le flux.

Si les opérateurs ont besoin d'accéder à des membres privés, ils doivent être déclarés friend de la classe, ou alors utiliser des accesseurs.

Exemple :

#include <iostream>

class Foo {
    int m_bar;
public:
    Foo (int bar) : m_bar {bar} {};

    friend std::ostream& operator<< (std::ostream& out, const Foo& foo);
    friend std::istream& operator>> (std::istream& in, Foo& foo);
};

std::ostream& operator<< (std::ostream& out, const Foo& foo)
{
    out << "bar = " << foo.m_bar;
    return out;
}

std::istream& operator>> (std::istream& in, Foo& foo)
{
    std::cout << "Entrez un entier : ";
    in >> foo.m_bar;
    return in;
}

int main()
{
    Foo foo {5};
    std::cout << foo << "\n";       // bar = 5
    std::cin >> foo;                // Entrez un entier : 7
    std::cout << foo << "\n";       // bar = 7
}

11.4. Compléments

Les cas d'usage avec des opérateurs surchargés sont synthétisés dans ce tableau.

La surcharge des opérateurs a des limitations :

• les opérations doivent conserver leur signification, par exemple + pour faire une addition ;
• il n'est pas possible de changer la priorité ni le nombre d'opérandes d'un opérateur ;
• on ne peut pas créer de nouveaux opérateurs (**, <>, etc) ;
• certains opérateurs ne peuvent pas être surchargés : :: (portée), . (accès de membre), ? : (condition ternaire) ;
• la surcharge des opérateurs && et || fait perdre l'évaluation rapide (ou encore court-circuit : l'évaluation de gauche à droite s'arrête dès que le résultat est sûr).

12. Itérateurs

Un itérateur est un objet qui facilite l'itération sur un conteneur. Il présente une interface qui permet de s'abstraire des opérations internes de l'itération :

• la méthode begin() fournit un pseudo-pointeur sur le premier élément ;
• la méthode end() fournit un pseudo-pointeur marqueur de fin ;
• l'opérateur ++ est surchargé pour passer à l'élément suivant ;
• l'opérateur != est surchargé pour la condition d'arrêt ;
• l'opérateur de déréférencement * est surchargé pour donner la valeur.

On qualifie les valeurs renvoyées de pseudo-pointeur car elle peuvent être déréférencées, mais ne sont en général pas un pointeur.

Exemple avec un std::vector :

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {5, 7, 11};

    for (auto p = v.begin(); p != v.end(); p++) {
        std::cout << *p << " ";
    }
    std::cout << std::endl;         // 5 7 11
}

Le type de p dans la boucle est std::vector<int>::iterator.

Il n'est pas possible d'afficher p avec std::cout car l'opérateur << n'est pas défini pour un iterator.

12.1. Conteneurs de la librairie standard

Les conteneurs de la librairie standard fournissent tous un itérateur avec la paire begin() end() ; il peuvent parfois en fournir plusieurs, par exemple la paire rbegin() rend() itère dans le sens inverse :

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {5, 7, 11};

    for (auto p = v.rbegin(); p != v.rend(); p++) {  // en arrière
        std::cout << *p << " ";
    }
    std::cout << std::endl;         // 11 7 5
}

Le type de p dans la boucle est std::vector<int>::reverse_iterator.

Certains conteneurs de la librairie standard possèdent des méthodes utilisant des itérateurs dans leurs arguments ; par exemple la classe std::vector :

• c.insert (c.begin()+i, value) : insère value à l'indice i dans c, en décalant les éléments suivants ;
• c.erase (c.begin()+i) : supprime l'élément à l'indice i dans c, en décalant les éléments suivants.

Autre exemple avec les classes std::list et std::deque :

• c.insert(std::next(c.begin(), i), value) : insère value en position i dans c ;
• c.erase(std::next(c.begin(), i)) : supprime l'élément en position i dans c.

La fonction std::sort utilise des itérateurs : on peut trier le contenu d'un conteneur c dans l'ordre donné par l'opérateur < en appelant :

sort (c.begin(), c.end());

La fonction std::find cherche une valeur value dans un conteneur c avec l'opérateur == en écrivant

auto p = find (c.begin(), c.end(), value);

le résultat p est égal à c.end() si la valeur n'est pas trouvée.

12.2. Boucles range-for

Tous les types qui définissent un itérateur peuvent aussi être utilisés avec un range-for, tel que

for (auto& element : collection) ...;

qui est (grossièrement) traduit en :

for (auto a = collection.begin(), b = collection.end(); a != b ; a++) {
    auto& element = *a;
    ...
}

Application : ceci nous donne un moyen pour écrire une classe template capable d'itérer à l'envers (inspirée du C++20 avec std::ranges::reverse_view) :

#include <iostream>
#include <vector>

template <class T>
class Reverse {
private:
    T& m_object;
public:
    Reverse (T& object) : m_object(object) {}
    auto begin() { return m_object.rbegin(); }
    auto end()   { return m_object.rend(); }
};

int main()
{
    std::vector<int> v {5, 7, 11};

    for (auto& x : v) {             // par référence -> sans recopie
        std::cout << x << " ";
    }
    std::cout << std::endl;         // 5 7 11

    for (auto& x : Reverse(v)) {    // par référence -> sans recopie
        std::cout << x << " ";
    }
    std::cout << std::endl;         // 11 7 5
}

12.3. Construction d'un itérateur

L'implémentation d'un itérateur sur un conteneur dépend de la nature du conteneur.

Cela peut être un simple pointeur, par exemple sur un tableau ; on profite alors de l'arithmétique des pointeurs :

#include <iostream>

template <typename T>
class MyCont {
    T* m_v;
    std::size_t m_size;
public:
    MyCont (T* v, std::size_t size) : m_v {v}, m_size {size} {};
    T* begin() { return m_v; }
    T* end()   { return m_v+m_size; }
};

int main()
{
    int v[] {5, 7, 11};
    auto c = MyCont (v, 3);

    for (auto p = c.begin(); p != c.end(); p++)
        std::cout << *p << " ";
    std::cout << std::endl;         // 5 7 11
}

Une autre implémentation peut être faite en mémorisant un indice ; il faut alors définir une classe imbriquée pour la paire begin() end() et surcharger les opérateurs ++, != et * (déréférencement) :

#include <iostream>

template <typename T>
class MyCont {
    T* m_v;
    std::size_t m_size;
public:
    class MyIter {            // classe imbriquée
        std::size_t m_idx;
        MyCont& m_outer;      // classe externe
    public:
        MyIter (std::size_t idx, MyCont& outer) : 
            m_idx {idx}, m_outer {outer} {};
        MyIter operator++ (int) { m_idx++; return *this;}
        bool operator!= (MyIter other) { return m_idx != other.m_idx; }
        T& operator* () { return *(m_outer.m_v+m_idx); }
    };
    MyCont (T* v, std::size_t size) : m_v {v}, m_size {size} {};
    MyIter begin() { return MyIter {0, *this}; }
    MyIter end()   { return MyIter {m_size, *this}; }
};

int main()
{
    int v[] {5, 7, 11};
    auto c = MyCont (v, 3);

    for (auto p = c.begin(); p != c.end(); p++)
        std::cout << *p << " ";
    std::cout << std::endl;         // 5 7 11
}

Remarque : il est plus simple d'utiliser std::array (tableau de taille fixe) qui définit directement un itérateur.

Plus généralement, la librairie standard définit la classe de base std::iterator qui simplifie (ou du moins, standardise) la définition d'itérateurs.

12.4. Compléments

Lors d'une itération, si le conteneur change, ou si l'élément courant change d'adresse ou est détruit, l'itérateur pourrait ne plus être utilisable sans provoquer un comportement indéfini. On dit alors que l'itérateur est invalidé.

La documentation des itérateurs de la librairie standard décrit quelles sont les opérations qui invalident un itérateur pour chacun des conteneurs, voir par exemple pour les vecteurs.

On peut ranger les itérateurs en différentes catégories (C++17) :

• input iterator : on peut lire une valeur dans l'itérateur (std::cout << *p) ;
• output iterator : on peut écrire une valeur dans l'itérateur (*p = some_value;) ;
• input output iterator : on a les 2 propriétés ;
• forward iterator : est un input operator qui supporte l'incrément (p++) ;
• bidirectional iterator : est un forward iterator qui supporte aussi le décrément (p--) ;
• random access iterator : est un bidirectional iterator qui permet d'accéder à tout élément en temps contant (v.begin()+i) ;
• contiguous iterator : est un random access iterator dont les éléments adjacents sont aussi adjacents en mémoire.

Exemple de conteneurs possédant un contiguous iterator : array, string, vector.

Le C++20 définit une nouvelle catégorisation des itérateurs à partir de concepts.