Le carnet On est …
Séance 7 · encre bleue

Templates & STL

Programmation générique en C++ : fonctions et classes paramétrées par type, la bibliothèque standard (vector, list, map, deque), itérateurs, foncteurs, algorithmes. Bonus : héritage multiple virtuel.

~ 70 min Source : Cours7 Templates STL + TP7 + examen 2024 17 flashcards · 10 QCM

📄 Ressources du cours

📥 Télécharger les slides  ·  🔗 Ouvrir dans un nouvel onglet  ·  📝 Ouvrir le TD/TP

🎥 Vidéos recommandées

1. Pourquoi les templates ?

Définition Un template permet d'écrire une fonction ou une classe paramétrée par un (ou plusieurs) types. Le compilateur génère ensuite une version pour chaque type concret utilisé. C'est la programmation générique.

Trois bénéfices :

  • performance — code compact et efficace (pas de double dispatch)
  • temps de codage — une seule version pour tous les types
  • clarté — l'intention algorithmique se lit d'un coup
📌 Polymorphisme paramétrique vs polymorphisme d'héritage
En CM4, le polymorphisme était dynamique (résolu au runtime via virtual). Avec les templates, il est statique (résolu à la compilation). Mêmes intentions ; mécanismes très différents.

2. Fonction template

Syntaxe : on préfixe la fonction par template <typename T> (ou template <class T>, équivalent).

// dans un fichier .h
template <typename T>
T min(const T& a, const T& b) {
   return (a < b ? a : b);
}

Instanciation

int    minimum1 = min<int>(3, 7);          // version int générée
double minimum2 = min<double>(3.5, 2.1);   // version double générée
Personne pmin   = min<Personne>(p1, p2);    // nécessite operator< sur Personne
⚠ Contrainte implicite Le code a < b dans le template suppose que le type T supporte operator<. Si on appelle min<MaClasse> et que MaClasse ne définit pas <, le compilateur produit une erreur dans l'instanciation, pas dans le template.

Plusieurs paramètres de type

template <typename T1, typename T2>
T2 calculerMoyenne(T1 tableau[], int taille) {
   T2 somme = 0;
   for (int i = 0; i < taille; ++i)
      somme += tableau[i];
   return somme / taille;
}

// utilisation : tableau d'int, moyenne en double
int tab[5] = {1, 2, 3, 4, 5};
double avg = calculerMoyenne<int, double>(tab, 5);   // avg = 3.0

3. Classe template

On peut paramétrer une classe entière. Exemple historique : un Vector qui contient des double, généralisé en Vector<T>.

Version concrète — Vector de double

class Vector {
   private:
      double* elem;
      unsigned int size;
   public:
      Vector(unsigned int s);
      ~Vector();
      double& operator[](unsigned int i);
      unsigned int getSize() const;
};

Version template — Vector<T>

template <typename T>
class Vector {
   private:
      T* elem;
      unsigned int size;
   public:
      Vector(unsigned int s);
      ~Vector() { delete[] elem; }
      T& operator[](unsigned int i);
      const T& operator[](unsigned int i) const;
      unsigned int getSize() const { return size; }
};

// implémentation en dehors — chaque méthode reprend le template<...>
template <typename T>
Vector<T>::Vector(unsigned int s) : elem{new T[s]}, size{s} { }

template <typename T>
const T& Vector<T>::operator[](unsigned int i) const {
   if (i >= size)
      throw out_of_range{"Vector::operator[]"};
   return elem[i];
}

Utilisation

Vector<char>      vc(200);   // vecteur de 200 caractères
Vector<string>    vs(17);    // vecteur de 17 strings
Vector<list<int>> vli(45);   // vecteur de 45 listes d'entiers
Tout dans le .h ! Pour les templates, l'implémentation des méthodes doit être visible au point d'instanciation. Conséquence pratique : on met tout dans le .h. Pas de .cpp séparé comme pour les classes classiques.

4. La STL — Standard Template Library

🔑 La devise (Stroustrup)
« Don't reinvent the wheel. »
La STL fournit algorithmes et structures de données fondamentaux, bien codés, testés, optimisés. On l'utilise plutôt que de coder ses propres listes/tris.

Quatre composants :

ComposantRôleExemples
Conteneursstructures de donnéesvector, list, map, set, stack…
Itérateursparcourir un conteneur uniformémentbegin(), end(), ++, *
Algorithmesopérations sur des plages d'itérateurssort, count, find, copy…
Foncteursobjets qui se comportent comme des fonctionsgreater<T>, prédicats custom

5. Conteneurs — séquentiels et associatifs

Deux familles
  • Séquentiels : les éléments sont ordonnés par insertion. Insertion/suppression à un endroit explicite. vector, list, deque, stack, queue.
  • Associatifs : les éléments sont indexés par une clé. set, multiset, map, multimap.

Fonctionnalités communes : size(), empty(), clear(), begin(), end()…

Conteneur séquentiel — list

#include <list>

list<int> l;
for (int i = 0; i < 5; i++)
   l.push_back((10 + 2*i) % 5 + i);   // {0, 3, 5, 4, 1}

l.sort();                       // {0, 1, 3, 4, 5}
l.reverse();                    // {5, 4, 3, 1, 0}
cout << l.front() << " " << l.back();    // "5 0"

Conteneur séquentiel — vector

Le plus utilisé. Accès indexé en O(1), insertion en fin amortie en O(1). Méthodes clés :

MéthodeRôle
push_back(x)ajoute à la fin
pop_back()retire le dernier
operator[](i)accès direct à l'index i
front() / back()premier / dernier élément
size() / empty()nombre d'éléments / test de vacuité
clear() / erase(it)vider / retirer à un itérateur

Conteneur associatif — map

#include <map>

map<string, string> repertoire;
repertoire["Jean Martin"]     = "01.02.03.04.05";
repertoire["François Martin"] = "02.03.04.05.06";
repertoire["Louis Dupont"]    = "03.04.05.06.07";

repertoire.insert(pair<string, string>("Louis Martin", "04.05.06.07.08"));

6. Itérateurs — parcourir uniformément

Définition Un itérateur est un objet qui pointe sur un élément d'un conteneur et sait passer au suivant. Il offre les opérateurs ++ (avancer) et * (déréférencer). Chaque conteneur définit son propre type, mais l'interface est la même. 
vector<int>::iterator        it1;     // itérateur sur vector<int>
map<string, int>::iterator   it2;     // sur map<string, int>
deque<char>::iterator       it3;     // sur deque<char>
list<double>::iterator     it4;     // sur list<double>

Le pattern begin() / end()

#include <deque>
#include <iostream>
using namespace std;

int main() {
   deque<int> d(5, 6);          // 5 éléments valant 6
   deque<int>::iterator it;

   for (it = d.begin(); it != d.end(); ++it) {
      cout << *it << endl;       // déréférencement avec *
   }
   return 0;
}
🔑 end() est après le dernier
Convention universelle : begin() pointe sur le premier élément, end() sur la position juste après le dernier (sentinelle). Le test de fin est donc it != end().

Random access iterators

Les itérateurs des vector et deque supportent en plus + et - pour sauter de plusieurs positions.

vector<int> tab(100, 2);
vector<int>::iterator it = tab.begin() + 7;    // 8e élément

7. Foncteurs — un objet qui se comporte comme une fonction

Définition Un foncteur (function object) est un objet d'une classe qui surcharge operator(). On peut alors l'appeler comme une fonction : monObjet(args).

Exemple minimal

// addition.h
class Addition {
   public:
      int operator()(int a, int b) {
         return a + b;
      }
};

// main.cpp
Addition add;
int a = 2, b = 3;
cout << a << " + " << b << " = " << add(a, b);  // "2 + 3 = 5"

Foncteur avec état

Contrairement à une fonction, un foncteur peut avoir des attributs — donc une mémoire entre les appels.

class Remplir {
   private: int val;
   public:
      Remplir(int i) : val{i} { }
      int operator()() {
         ++val;
         return val;
      }
};

vector<int> tab(10, 0);
Remplir f(0);
for (auto it = tab.begin(); it != tab.end(); ++it) {
   *it = f();          // remplit avec 1, 2, 3, ... 10
}

Foncteur générique — greater<T>

La STL fournit des foncteurs prêts à l'emploi dans <functional> : greater, less, equal_to, etc.

template <class T>
class greater {
   public:
      bool operator()(const T& x, const T& y) const {
         return x > y;
      }
};

8. Algorithmes — fonctions templates qui mangent des plages

En-tête : <algorithm>. Tous les algorithmes opèrent sur un intervalle d'itérateurs [begin, end).

Compter

#include <algorithm>

vector<int> v;
int n = count(v.begin(), v.end(), 1);          // nombre d'occurrences de 1

list<double> l;
int m = count(l.begin(), l.end(), 3.5);        // idem pour 3.5

Trier avec un foncteur de comparaison

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

vector<int> v = {1, 5, 2, 4, 3};

sort(v.begin(), v.end(), greater<int>());    // décroissant — {5, 4, 3, 2, 1}
sort(v.begin(), v.end());                       // défaut = operator< → croissant

Itération moderne — for (auto x : ...)

for (auto value : v) {
   cout << value << endl;
}

Équivalent compact du for (it = v.begin(); it != v.end(); ++it). auto demande au compilateur de déduire le type.

9. Quel conteneur choisir ?

BesoinConteneur recommandé
Accès indexé rapide, ajout en finvector
Insertion/suppression fréquente au milieulist
Ajout/retrait aux deux boutsdeque
LIFO (dernier entré premier sorti)stack
FIFO (premier entré premier sorti)queue
Le plus prioritaire d'abordpriority_queue
Ensemble trié sans doublonsset
Ensemble trié avec doublonsmultiset
Dictionnaire clé → valeurmap
Dictionnaire avec clés en doublonmultimap
📌 Règle de pouce
Par défaut, prendre vector. Passer à autre chose seulement si le profil d'usage (insertions au milieu, clé d'accès…) le justifie. vector est presque toujours le plus rapide en pratique grâce à la cache friendliness.

10. Bonus — héritage multiple virtuel (problème du diamant)

L'examen 2024 exo 5 demande de bâtir PointFormeCol qui hérite à la fois de PointForme et PointCol, eux-mêmes dérivés de Point. Sans précaution, Point serait inclus deux fois dans PointFormeCol : les attributs x, y deviendraient ambigus.

Point PointCol PointForme PointFormeCol

Solution — le mot-clé virtual dans la dérivation

En écrivant virtual public Point dans les classes intermédiaires, on demande à C++ de partager une seule copie de Point au final.

// point.h
class Point {
   protected:
      short x = 0, y = 0;
   public:
      Point() { }
      Point(short abs, short ord) : x{abs}, y{ord} { }
      virtual void decrire() { cout << "point (" << x << "," << y << ")\n"; }
      virtual ~Point() { }
};

// pointcol.h — virtual public Point
class PointCol : virtual public Point {
   protected: unsigned int color;
   public:
      PointCol(short a, short o, unsigned int c) : Point(a, o), color{c} { }
      virtual void decrire() override {
         cout << "point coloré (" << x << "," << y << ") couleur " << color << endl;
      }
};

// pointforme.h — virtual public Point aussi
class PointForme : virtual public Point {
   protected: char forme;
   public:
      PointForme(short a, short o, char f) : Point(a, o), forme{f} { }
      virtual void decrire() override {
         cout << "point avec forme '" << forme << "' (" << x << "," << y << ")\n";
      }
};

// pointformecol.h — hérite des deux
class PointFormeCol : public PointForme, public PointCol {
   public:
      PointFormeCol(short a, short o, char f, unsigned int c)
         : Point(a, o), PointForme(a, o, f), PointCol(a, o, c) { }
      virtual void decrire() override {
         cout << "point coloré avec forme '" << forme
              << "' (" << x << "," << y << ") couleur " << color << endl;
      }
};

Polymorphisme + STL en action

#include <vector>

int main() {
   vector<Point*> LPs;

   LPs.push_back(new Point(3, 5));
   LPs.push_back(new PointCol(3, 5, 3));
   LPs.push_back(new PointForme(5, 6, 'o'));
   LPs.push_back(new PointFormeCol(5, 6, 9, 'x'));

   for (auto it = LPs.begin(); it != LPs.end(); ++it) {
      (*it)->decrire();      // chaque objet décrit sa propre forme (polymorphisme)
   }
   // + delete sur chaque pointeur, idéalement
}
⚠ Sans virtual dans l'héritage intermédiaire PointFormeCol aurait deux sous-objets Point : this->x serait ambigu (lequel ? celui hérité via PointCol ou via PointForme ?). Le compilateur refuse de compiler.

★ Réviser le chapitre

Pour vérifier ta compréhension

Quelle est la différence entre un template de fonction et un template de classe ?

Template de fonction : génère plusieurs versions d'une fonction selon le type des arguments. Template de classe : génère plusieurs versions d'une classe selon le type paramètre. Syntaxe commune : template <typename T> avant la définition.

Quand utiliser std::vector vs std::list ?

vector : accès aléatoire O(1), insertion à la fin O(1) amortie, mais insertion au milieu O(n). À privilégier dans la plupart des cas. list : insertion/suppression au milieu O(1) (si on a l'itérateur), mais accès aléatoire O(n). Utile uniquement si on insère/supprime beaucoup au milieu.

Qu'est-ce qu'un itérateur en C++ ?

Un objet qui se comporte comme un pointeur généralisé sur les éléments d'un conteneur. Permet de parcourir un conteneur uniformément : for (auto it = v.begin(); it != v.end(); ++it) { /* *it */ }. Existe en plusieurs catégories : input, forward, bidirectional, random access.

Quelle est la différence entre std::map et std::unordered_map ?

map : implémenté avec un arbre rouge-noir. Tri automatique des clés. Opérations en O(log n). unordered_map : implémenté avec une table de hachage. Pas d'ordre. Opérations en O(1) en moyenne. Choisir unordered_map si l'ordre des clés est sans importance.

Que sont les algorithmes STL et comment les utiliser ?

Fonctions génériques travaillant sur des plages d'itérateurs : std::sort, std::find, std::transform, std::accumulate, etc. Exemple : std::sort(v.begin(), v.end());. Ils découplent algorithme et conteneur : un même algo fonctionne sur vector, list, array…

🃏 Flashcards

Syntaxe d'une fonction template ?
template <typename T> T f(T a) { ... }. typename et class sont équivalents dans ce contexte.
Quand le code template est-il vraiment compilé ?
À l'instanciation, pas à la déclaration. Le compilateur génère une version par type concret utilisé (min<int>, min<double>…).
Pourquoi tout mettre dans le .h pour les templates ?
Le compilateur a besoin de voir la définition complète au point d'instanciation pour générer le code. Sans visibilité du corps, erreur de lien.
Syntaxe d'une classe template ?
template <typename T> class C { ... };. À l'extérieur, les méthodes commencent toutes par template <typename T> puis RetType C<T>::nom(...).
Que veut dire l'acronyme STL ?
Standard Template Library. Bibliothèque standard du C++ fournissant conteneurs, itérateurs, algorithmes, foncteurs.
Différence conteneur séquentiel / associatif ?
Séquentiel : éléments ordonnés par insertion (vector, list, deque). Associatif : éléments indexés par une clé (map, set).
À quoi sert un itérateur ?
À parcourir un conteneur de façon uniforme. Opérateurs principaux : ++ (avancer), * (déréférencer), !=. Chaque conteneur expose begin() et end().
Où pointe end() ?
Juste après le dernier élément (sentinelle). Le test de fin est donc it != end(). end() ne se déréférence jamais.
Qu'est-ce qu'un foncteur ?
Un objet d'une classe qui surcharge operator(). On l'appelle comme une fonction. Avantage : il peut porter un état entre appels (attributs).
Quel en-tête pour les algorithmes STL ?
<algorithm>. Tous les algorithmes opèrent sur un intervalle d'itérateurs [begin, end).
Comment trier un vector<int> en décroissant ?
sort(v.begin(), v.end(), greater<int>());. Sans foncteur, sort utilise operator< et trie en croissant.
Conteneur LIFO ? FIFO ?
LIFO (pile) → stack. FIFO (file) → queue. Plus prioritaire d'abord → priority_queue.
Qu'est-ce que le « problème du diamant » ?
Quand une classe D hérite de B et C, qui héritent toutes deux de A, sans précaution D contient deux copies des attributs de A. Les accès deviennent ambigus.
Solution au diamant en C++ ?
L'héritage virtuel : class B : virtual public A. Garantit qu'une seule copie de A existera dans toute classe dérivant de B et de C.
Dans PointFormeCol qui hérite de PointForme et PointCol (eux-mêmes via virtual de Point), qui appelle le constructeur de Point ?
La classe la plus dérivée, donc PointFormeCol elle-même. Il faut écrire : Point(a, o), PointForme(...), PointCol(...) dans son constructeur.
Comment itérer modernement sur un vector<int> v ?
for (auto value : v) { ... }. auto déduit le type. Équivalent au triple for (it = ..., it != ..., ++it).
Conteneur par défaut à choisir si aucune contrainte ?
vector. Cache-friendly, accès indexé en O(1), push_back amorti en O(1). Passer à autre chose seulement si le profil d'usage l'exige.

✎ Quiz éclair

1.Quelle syntaxe déclare une fonction template ?
  • generic T f(T a) { ... }
  • auto T f(auto a) { ... }
  • template <typename T> T f(T a) { ... }
  • function<T> f(T a) { ... }
La syntaxe canonique. typename peut être remplacé par class sans changer le sens dans cette position.
2.Quand le compilateur génère-t-il le code d'un template ?
  • À la déclaration du template
  • À chaque instanciation avec un type concret
  • Au démarrage du programme
  • Au premier appel runtime
C'est ce qui rend les templates aussi rapides que du code écrit à la main : le polymorphisme paramétrique est résolu à la compilation.
3.Pourquoi met-on toute l'implémentation d'un template dans le .h ?
  • Pour la performance
  • Par convention seulement
  • Pour réduire le binaire
  • Le compilateur a besoin de voir la définition complète à l'instanciation
Sans la définition visible, le compilateur ne peut pas générer le code pour un type donné — erreur de lien.
4.Quel conteneur pour un accès indexé rapide à des éléments ajoutés en fin ?
  • vector
  • list
  • map
  • set
vector offre operator[] en O(1) et push_back en O(1) amorti. list est meilleure pour les insertions au milieu mais l'accès indexé est en O(n).
5.Pour déclarer un itérateur sur un vector<int> :
  • vector::iterator<int> it;
  • iterator<vector<int>> it;
  • vector<int>::iterator it;
  • int* it;
Le type iterator est imbriqué dans la classe template vector<T>.
6.Où pointe v.end() ?
  • Sur le dernier élément
  • Juste après le dernier élément (sentinelle)
  • Sur le premier élément invalide
  • nullptr
Convention universelle des plages C++ : intervalle semi-ouvert [begin, end). end() ne se déréférence jamais.
7.Un foncteur est :
  • Une fonction renvoyant une autre fonction
  • Un pointeur sur fonction
  • Un objet d'une classe qui surcharge operator()
  • Un alias pour std::function
Surcharge de () = appel possible comme une fonction. Avantage sur une fonction libre : on peut porter un état entre appels.
8.Comment résoudre le problème du diamant ?
  • Avec un constructeur privé
  • Avec final sur la classe de base
  • En déclarant les classes friend
  • Avec l'héritage virtuel : class B : virtual public A
L'héritage virtuel garantit qu'une seule copie de la classe de base existera, peu importe combien de chemins d'héritage y mènent.
9.Dans PointFormeCol avec héritage virtuel sur Point, qui appelle le constructeur de Point ?
  • PointFormeCol directement, dans sa liste d'initialisation
  • PointCol
  • PointForme
  • Personne : Point est abstrait
Avec héritage virtuel, la classe la plus dérivée est responsable de l'initialisation de la base virtuelle. Les constructeurs intermédiaires n'ont aucune influence.
10.Comment trier en croissant un vector<int> v avec un algorithme STL ?
  • v.sort();
  • sort(v.begin(), v.end());
  • std::ascending(v);
  • v.order();
std::sort de <algorithm> prend une plage d'itérateurs. vector n'a pas de méthode sort membre (contrairement à list).

Score : 0 / 10 ·