Les éléments de C++

Ce module ne t'apprend pas le C++. Il t'apprend à lire les quinze lignes qui vont revenir, presque à l'identique, dans chaque structure de données du reste de la session : une classe, un pointeur, un new, un destructeur. Quatre choses, et elles se répètent jusqu'au dernier module.

Un rappel, pas un cours de langage

Commençons par la question que tout le monde se pose en ouvrant le premier travail pratique : pourquoi le C++, alors qu'on sait déjà programmer dans un langage plus confortable ? La réponse n'est pas historique, et elle n'est pas non plus une question de vitesse. Elle tient au fait que ce cours-ci ne porte pas sur des programmes, mais sur des structures — et qu'une structure de données est faite de mémoire et de liens entre morceaux de mémoire.

Trois raisons concrètes, et les trois se retrouvent dans les modules qui suivent. La première est le contrôle explicite de la mémoire : c'est toi qui décides quand un nœud naît et quand il meurt, donc tu peux le lire dans le code au lieu de le deviner. La deuxième est la généricité : une seule implémentation d'arbre sert pour des entiers, des chaînes ou des dates, et on verra comment. La troisième est la bibliothèque standard, la STL, qui fournit déjà toutes les structures du cours — non pas pour t'éviter de les écrire, mais pour te donner un modèle d'interface : quand tu implémenteras une pile, tu la nommeras comme la STL nomme la sienne.

Un mot sur la façon de lire ce qui suit. Chaque bloc de code de ce module est précédé d'une phrase qui dit pourquoi il est là et ce qu'il faut y regarder. Ce n'est pas une politesse : quinze lignes de C++ qu'on lit sans savoir ce qu'on cherche ne laissent rien. Lis la phrase, puis le code, puis les commentaires — et si tu n'as le temps que d'une des trois choses, garde la phrase.

Deux mémoires, deux durées de vie

Voici le problème qui rend tout le reste nécessaire. Tu écris une fonction qui doit créer un nœud et le raccrocher à une liste. La fonction se termine ; la liste, elle, doit continuer d'exister. Or une variable déclarée dans une fonction disparaît quand la fonction se termine — c'est la règle, et elle est absolue.

Il faut donc un endroit où poser des objets qui ne suivent pas le sort de la fonction qui les a créés. C'est pour ça que la mémoire d'un programme est coupée en deux régions aux règles opposées : la pile et le tas.

Le point qui compte vraiment n'est dans aucune de ces deux colonnes : c'est ce qui se passe entre elles. Quand tu écris Noeud* n = new Noeud(5); dans une fonction, deux choses distinctes sont créées, dans deux régions différentes. Le nœud est dans le tas. La variable n, qui n'est qu'une adresse, est sur la pile. À la fin de la fonction, la pile est vidée : n disparaît. Le nœud, lui, ne bouge pas.

Tout dépend alors d'une seule chose : est-ce que quelqu'un d'autre connaît encore l'adresse de ce nœud ? Si tu l'as raccroché à une liste avant de sortir, oui — et c'est exactement ce qu'on veut. Sinon, le nœud existe toujours et plus personne ne peut l'atteindre : il est perdu. La figure ci-dessous met les trois moments côte à côte.

int sommeDesDeux(int a, int b) {
  int* resultat = new int(a + b);
  return *resultat;
}

Ce que chaque symbole te dit

Quatre écritures reviennent partout dès qu'il y a un pointeur, et elles se ressemblent assez pour qu'on les confonde en lisant vite. Voici ce que chacune dit, en une ligne — c'est un rappel, pas une découverte : on va vite pour arriver à ce qui suit, qui l'est moins.

La quatrième ligne mérite qu'on s'y arrête, parce qu'elle n'est pas une précaution d'écriture : elle est la raison pour laquelle les structures de données emploient des pointeurs plutôt que des références. nullptr est une valeur qu'un pointeur peut légitimement porter, et dans une liste chaînée elle signifie quelque chose — le dernier nœud pointe vers nullptr, et c'est ainsi qu'on sait qu'on est arrivé au bout. Un arbre dont le fils gauche vaut nullptr n'a pas de fils gauche. Le « rien » est une information du modèle, pas une erreur.

La référence, elle, ne peut pas porter cette information. Une référence — notée T& — est un autre nom pour une variable qui existe déjà ; elle est attachée à sa cible au moment de sa création et ne peut plus en changer, ni valoir « rien ». C'est une limitation, et c'est aussi ce qui la rend sûre. D'où la règle de lecture :

• Une référence quand la chose existe forcément et qu'on ne changera pas de cible : le paramètre d'une fonction, la valeur qu'on veut modifier sur place.
• Un pointeur quand « rien » est une réponse possible ou quand la cible change : les liens d'une liste, les fils d'un arbre, le sommet d'une pile.

Reste la forme que tu vas croiser le plus souvent de tout le cours, et qui n'est expliquée nulle part parce qu'elle a l'air anodine : const T& en paramètre. Le bloc ci-dessous met les trois façons de recevoir un objet l'une sous l'autre — regarde uniquement ce que chaque signature promet, le corps des fonctions n'a aucun intérêt ici.

// 1. PAR VALEUR — la fonction reçoit une copie complète.
//    Sûr, et coûteux : copier un objet qui contient mille éléments
//    en recopie mille. Modifier `element` ne change rien chez l'appelant.
void ajouter(Element element);

// 2. PAR RÉFÉRENCE — aucun objet copié, la fonction travaille sur
//    l'original. C'est ce qu'on veut pour MODIFIER.
void remplir(Element& element);

// 3. PAR RÉFÉRENCE CONSTANTE — aucun objet copié, et interdiction
//    d'y toucher. Le compilateur refuse toute modification.
void afficher(const Element& element);

La troisième forme est le défaut de tout le cours : elle a le prix de la deuxième et la sûreté de la première.

Le raisonnement tient en deux temps. Passer par valeur copie, donc coûte le prix d'une copie ; passer par référence ne copie rien, donc coûte le prix d'une adresse, quelle que soit la taille de l'objet. Mais la référence nue autorise la fonction à modifier ton objet, ce qui n'est pas ce que tu veux quand tu voulais seulement le lire. Le const ferme cette porte : la fonction voit l'original, et le compilateur refuse qu'elle y touche.

int a = 10;
int b = 20;
int* p = &a;
int& r = b;

p = &b;      // (1)
r = a;       // (2)

Allouer et libérer : le contrat

Le tas ne se remplit pas tout seul : on y prend de la place avec new, et on la rend avec delete. Ces deux mots forment un contrat, et le contrat n'a qu'une clause : à chaque new correspond exactement un delete. Ni zéro — c'est une fuite —, ni deux — c'est un plantage.

Le bloc suivant est le vocabulaire complet de l'allocation dans ce cours : il n'y a rien de plus à connaître, et les six lignes se répondent deux à deux.

// Un objet seul, avec l'argument de son constructeur.
Noeud* n = new Noeud(5);
delete n;                    // rend la place, appelle le destructeur de Noeud

// Un TABLEAU de n objets. Les crochets sont dans les deux écritures,
// et ils doivent l'être : c'est ce qui distingue les deux cas.
int* donnees = new int[100];
delete[] donnees;

// Après un delete, le pointeur contient encore l'ancienne adresse —
// une adresse qui ne t'appartient plus. On le neutralise.
n = nullptr;

Trois gestes seulement : allouer, libérer avec la forme qui correspond, neutraliser le pointeur devenu invalide.

La paire new[] / delete[] mérite une explication, parce que la règle est toujours donnée comme un interdit — « ne mets pas delete sur un tableau » — sans jamais dire ce qui se passerait. Voici ce qui se passe. Quand tu alloues un tableau, le programme retient quelque part combien d'éléments il contient ; c'est delete[] qui va lire ce nombre, pour appeler le destructeur de chacun des éléments avant de rendre la place. delete tout seul ne lit pas ce nombre : il traite l'adresse comme celle d'un objet unique et n'appelle qu'un destructeur. Les autres ne sont jamais détruits, et la place n'est pas rendue correctement.

Les trois accidents de l'allocation ont chacun un nom, et tu les rencontreras sous ces noms-là.

• La fuite — un new sans delete. Le programme marche et grossit. C'est le piège de la section précédente.
• La double libération — deux delete sur la même adresse. Le premier rend la place, le second rend une place qui ne t'appartient plus. Plantage, immédiat ou différé selon la chance qu'on a.
• Le pointeur ballant — l'emploi d'un pointeur après son delete. L'adresse est encore là, la place a été reprise par autre chose, et tu lis ou écris dans les affaires du voisin. C'est le plus difficile à diagnostiquer des trois, parce que le symptôme apparaît loin de la cause.

Reste la question pratique : où écrit-on le delete ? La réponse gouverne toute la suite du cours, et elle est étonnamment simple. Une structure de données qui alloue de la mémoire est responsable de la rendre ; l'endroit prévu pour ça s'appelle le destructeur, et c'est le sujet de deux sections plus bas. Retiens la forme de la réponse : le new est dans une méthode d'insertion, le delete correspondant est dans le destructeur de la même classe. Les deux ne se lisent jamais côte à côte, et c'est normal.

Lire une classe, ligne par ligne

Toutes les structures de données du cours sont des classes, et elles ont toutes la même allure. Cette section décortique la plus simple d'entre elles — un nœud de liste — en s'arrêtant sur les trois endroits où l'on décroche généralement.

Voici la classe entière. Ne cherche pas à la comprendre d'un coup : les commentaires numérotent les trois endroits qu'on va reprendre juste après, et c'est là-dessus que porte toute la section.

class Noeud {
private:                              // caché de l'extérieur — le défaut d'une class
    int    valeur;
    Noeud* suivant;

public:                               // visible de l'extérieur
    // (1) Le constructeur, et sa LISTE D'INITIALISATION après les deux-points.
    Noeud(int v) : valeur(v), suivant(nullptr) { }

    // (2) Le `const` de FIN promet que la méthode ne modifie pas l'objet.
    int    getValeur()  const { return valeur; }
    Noeud* getSuivant() const { return suivant; }

    void setSuivant(Noeud* n) { suivant = n; }
};

Un nœud ne fait rien : il porte une valeur et un lien. Toute la logique vit dans la liste qui le contient.

(1) La liste d'initialisation. C'est la partie entre les deux-points et l'accolade ouvrante, et c'est de loin ce qui déroute le plus, parce que valeur(v) a exactement l'allure d'un appel de fonction. Ce n'en est pas un. Cette ligne se lit : « l'attribut valeur est construit à partir de v, l'attribut suivant est construit à partir de nullptr » — et tout cela se produit avant que la première ligne du corps ne s'exécute.

Pourquoi ne pas simplement écrire valeur = v; dans le corps ? Pour trois raisons, dans l'ordre où elles deviennent contraignantes. La première est une question de coût : les attributs sont construits de toute façon, avant le corps. Affecter dans le corps revient donc à les construire une première fois avec une valeur par défaut, puis à écraser ce travail — deux gestes au lieu d'un. Sur un int, personne ne le remarque ; sur un attribut qui est lui-même un objet lourd, c'est une construction complète jetée.

La deuxième raison est une obligation : un attribut déclaré const, ou un attribut qui est une référence, ne peut recevoir sa valeur qu'au moment de sa construction. Il n'y a alors aucune alternative — sans liste d'initialisation, le code ne compile pas. La troisième est de l'ordre de la lecture : la liste d'initialisation énumère, en un seul endroit et dans l'ordre, tous les attributs de la classe. Quand tu ouvres une structure inconnue, c'est la ligne qui te dit le plus vite de quoi elle est faite.

(2) Le const de fin. Il ne porte pas sur ce que la méthode renvoie — il porte sur l'objet lui-même, et se lit : « appeler cette méthode ne modifie pas l'objet ». Le compilateur vérifie cette promesse et refuse toute affectation à un attribut dans le corps d'une telle méthode.

Ce n'est pas une décoration, et la conséquence te tombera dessus tôt ou tard : souviens-toi que tout le cours passe ses objets en const T&. Sur une référence constante, seules les méthodes marquées const peuvent être appelées — les autres sont refusées, puisque rien ne garantit qu'elles ne modifieront pas l'objet. Oublier le const sur un accesseur produit donc une erreur de compilation qui apparaît ailleurs, dans la fonction qui essaie de s'en servir, et dont le message ne parle pas de l'accesseur. La règle pratique : toute méthode qui ne fait que lire reçoit un const, tout de suite.

(3) Le mot struct. Il n'est pas dans ce bloc, mais tu le verras dès la première liste chaînée : struct Noeud { … };. En C++, struct et class sont le même mécanisme, à une seule différence près — ce qui n'est pas explicitement rangé est public dans une struct, et private dans une class. La convention du cours en découle : struct pour un simple porteur de données comme un nœud, class pour tout ce qui a un comportement à protéger.

class Capteur {
private:
    const int  identifiant;    // ne changera jamais après la construction
    int        mesure;
public:
    // Version A
    Capteur(int id) : identifiant(id), mesure(0) { }

    // Version B
    Capteur(int id) {
        identifiant = id;
        mesure = 0;
    }
};

La règle des trois

On arrive à la section la plus importante du module, et à la seule dont l'oubli produit un programme qui plante sans qu'on ait écrit une ligne fautive. Le décor : une classe qui alloue de la mémoire dans son constructeur — c'est-à-dire toutes les structures de données du cours.

Le symptôme est connu. Une classe alloue un tableau, le libère dans son destructeur, et quelqu'un écrit Boite b = a;. Comme rien n'a été prévu pour la copie, C++ recopie les attributs un à un : b.donnees reçoit la même adresse que a.donnees. Un seul tableau, deux propriétaires, deux destructeurs — et delete[] appelé deux fois sur la même place. On appelle ça une copie superficielle : elle copie le pointeur, pas ce qu'il désigne.

Ce qu'il faut à la place s'appelle une copie profonde : allouer un second tableau et y recopier les valeurs, pour que les deux objets soient réellement indépendants. La figure ci-dessous met les deux régimes l'un à côté de l'autre ; l'adresse portée par chaque objet est ce qu'il faut lire.

D'où la règle des trois : si ta classe gère une ressource, tu dois écrire trois méthodes, et les trois ensemble. Le raisonnement qui l'impose est plus utile que la liste : le compilateur fournit une version par défaut de chacune des trois, et ces versions par défaut font toutes la même chose — une copie superficielle. Si tu n'en écris aucune, tu obtiens le régime de gauche sur la figure. Si tu n'en écris qu'une, tu obtiens un mélange des deux, ce qui est pire, parce que le programme fonctionne jusqu'au jour où quelqu'un copie ton objet.

Le bloc ci-dessous est la version complète et correcte. Il est plus long que les autres, et il n'a pas à être mémorisé ligne par ligne : ce qu'il faut y voir, c'est que les trois méthodes racontent la même histoire dans trois situations différentes — je meurs, je nais d'un autre, je remplace mon contenu par celui d'un autre.

class Boite {
private:
    int* donnees;
    int  taille;

public:
    Boite(int n) : taille(n) { donnees = new int[n]; }

    // 1. LE DESTRUCTEUR — appelé automatiquement à la mort de l'objet.
    ~Boite() { delete[] donnees; }

    // 2. LE CONSTRUCTEUR DE COPIE — appelé par `Boite b = a;`.
    //    On alloue NOTRE tableau, puis on recopie les valeurs.
    Boite(const Boite& autre) : taille(autre.taille) {
        donnees = new int[taille];
        for (int i = 0; i < taille; i++) donnees[i] = autre.donnees[i];
    }

    // 3. L'OPÉRATEUR D'AFFECTATION — appelé par `b = a;` sur un objet
    //    qui existe DÉJÀ. D'où deux gestes de plus que ci-dessus.
    Boite& operator=(const Boite& autre) {
        if (this != &autre) {          // (a) on ne s'écrase pas soi-même
            delete[] donnees;           // (b) on rend l'ancien tableau
            taille = autre.taille;
            donnees = new int[taille];
            for (int i = 0; i < taille; i++) donnees[i] = autre.donnees[i];
        }
        return *this;                   // (c) pour permettre a = b = c
    }
};

Le constructeur de copie fabrique un objet neuf ; l'opérateur d'affectation remplace le contenu d'un objet qui existait déjà. C'est cette différence qui explique les trois lignes marquées (a), (b) et (c).

Ces trois marques valent une explication, parce qu'elles reviennent à l'identique dans chaque operator= que tu écriras.

(a) this est un pointeur vers l'objet courant, disponible dans toute méthode : c'est la façon dont un objet se désigne lui-même. La condition compare donc l'adresse de l'objet à celle de la source, et protège contre l'auto-affectation, c'est-à-dire a = a;. Le cas paraît absurde écrit comme ça ; il ne l'est plus du tout sous la forme liste[i] = liste[j];, où i et j peuvent parfaitement être égaux. Sans cette ligne, la ligne suivante libérerait le tableau qu'on s'apprête à recopier.

(b) est le geste qui distingue l'affectation de la copie : l'objet possédait déjà un tableau, et si on n'en fait rien avant d'en allouer un autre, on vient d'écrire une fuite. Un operator= commence toujours par se débarrasser de ce qu'il détenait.

(c) return *this; renvoie l'objet lui-même — pas son adresse, d'où l'étoile. C'est ce qui permet d'écrire a = b = c; : l'affectation de droite produit une valeur, que celle de gauche peut à son tour utiliser. Sans ce retour, le chaînage ne compile pas.

class Sac {
    int* donnees;
public:
    Sac() { donnees = new int[100]; }
    ~Sac() { delete[] donnees; }
};

void traiter(Sac s) { /* ... */ }   // reçu PAR VALEUR

Sac sac;
traiter(sac);                        // et après cet appel ?

Le moule, et le type qu'il exige

Tu viens d'écrire une pile d'entiers. On te demande maintenant une pile de chaînes. Tu copies le fichier, tu remplaces int par string partout, et tu te retrouves avec deux fichiers dont la logique est identique au mot près. Puis on te demande une pile de dates.

Cette duplication est absurde : la structure d'une pile ne dépend pas de ce qu'elle contient. Empiler, dépiler, regarder le sommet : les trois gestes sont les mêmes pour des entiers et pour des dates. Le seul mot qui change est le nom du type. Les templates existent pour écrire ce mot une fois.

Voici le moule. Ce qu'il faut y regarder est la première ligne, et le fait que T se comporte ensuite exactement comme un nom de type ordinaire.

template<typename T>              // « T sera un type, décidé plus tard »
class Pile {
private:
    T*  donnees;                   // T s'emploie partout où irait un type
    int taille;
    int capacite;

public:
    Pile(int cap = 100) : taille(0), capacite(cap) {
        donnees = new T[cap];
    }
    ~Pile() { delete[] donnees; }

    void empiler(const T& valeur) { donnees[taille++] = valeur; }
    T    depiler()                { return donnees[--taille]; }
    bool estVide() const          { return taille == 0; }
};

Une seule écriture. T n'est pas un type : c'est un emplacement réservé pour un type.

Un détail de lecture avant d'aller plus loin, parce qu'il déroute au premier fichier qu'on ouvre : template<class T> et template<typename T> veulent dire exactement la même chose. Les deux mots sont interchangeables à cet endroit — pour des raisons purement historiques —, et tu croiseras les deux écritures dans le même cours. En particulier, T ne devient pas obligatoirement une classe parce qu'on a écrit class : Pile<int> reste parfaitement légal.

Ce qui se passe ensuite est le point que personne n'explique, et c'est pourtant lui qui rend le reste compréhensible. Quand tu écris Pile<int> nombres;, le compilateur ne se contente pas de « retenir » que T vaut int : il fabrique, à cet instant, une classe complète et neuve où chaque T a été remplacé par int. Cette fabrication porte un nom, l'instanciation. Si tu écris ensuite Pile<string> mots;, il en fabrique une deuxième, indépendante de la première.

De ce mécanisme découle une conséquence pratique qui déroute tout le monde une fois, et une seule : le corps des méthodes d'une classe template doit être visible dans le fichier d'en-tête. La raison est directe. Le compilateur ne fabrique la classe qu'au moment où il rencontre Pile<int>, c'est-à-dire dans ton fichier, pas dans celui de la pile. Pour la fabriquer, il lui faut le code complet sous les yeux à cet instant. S'il ne dispose que des signatures, il n'a rien à instancier.

void empiler(const T& valeur) { donnees[taille++] = valeur; }
T    depiler()                { return donnees[--taille]; }

Reste la moitié dont on parle rarement. Le template promet de fonctionner pour « n'importe quel type », mais ce n'est pas tout à fait vrai : il fonctionne pour n'importe quel type qui sait faire ce que le code lui demande. Une pile ne demande presque rien. Un arbre binaire de recherche, lui, doit décider si une valeur va à gauche ou à droite — il exécute donc if (valeur < noeud->valeur), et cela n'a de sens que si T sait se comparer.

C'est à quoi sert la surcharge d'opérateurs : donner un sens à <, == ou [] pour tes propres types. Le bloc ci-dessous ne montre qu'une chose : la forme que prend cette définition, et le fait qu'elle est une méthode ordinaire au nom inhabituel.

class Date {
private:
    int jour, mois, annee;

public:
    Date(int j, int m, int a) : jour(j), mois(m), annee(a) { }

    // « Est-ce que je viens avant `autre` ? » — ordre lexicographique :
    // l'année tranche ; à année égale, le mois ; à mois égal, le jour.
    bool operator<(const Date& autre) const {
        if (annee != autre.annee) return annee < autre.annee;
        if (mois  != autre.mois)  return mois  < autre.mois;
        return jour < autre.jour;
    }
};

// À partir de là, `d1 < d2` a un sens — et un arbre de Date compile.

Trois opérateurs suffisent pour tout le cours : < pour les structures ordonnées, == pour les recherches, [] pour l'accès indexé.

template<typename T>             // 1. générique : un moule, tous les types
class Conteneur {
private:
    T*  donnees;                  // 2. ce qu'on POSSÈDE, et qu'il faudra rendre
    int taille;

public:
    Conteneur(int n)              // 3. liste d'initialisation, PUIS allocation
        : taille(n) { donnees = new T[n]; }

    ~Conteneur() { delete[] donnees; }   // 4. le delete vit ICI, toujours

    void ajouter(const T& v);            // 5. on reçoit en const T&
    int  getTaille() const;              // 6. qui ne modifie pas est const
};

L'itérateur, et l'interface uniforme

Dernier outil du langage, et il répond à une question qui va se poser à chaque structure : comment parcourir ? Un tableau se parcourt par indice. Une liste chaînée n'a pas d'indice : on suit des pointeurs. Un arbre se parcourt en descendant. Trois structures, trois manières — et donc trois façons d'écrire la même boucle, ce qui interdit d'écrire une fonction qui marcherait sur les trois.

L'itérateur est la réponse : un objet qui désigne une position dans un conteneur, et qui sait avancer. Peu importe ce qu'il y a derrière — indice, pointeur, descente d'arbre —, il expose toujours les deux mêmes gestes.

Le bloc ci-dessous montre les trois écritures d'un même parcours, de la plus explicite à la plus courte. Elles font exactement la même chose ; ce qu'il faut retenir, c'est la première, parce que c'est celle dont les deux autres sont des abréviations.

vector<int> v = {10, 20, 30, 40};

// 1. La forme complète : on part du début, on s'arrête à la fin.
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    cout << *it;

// 2. `auto` demande au compilateur de deviner le type. Même boucle.
for (auto it = v.begin(); it != v.end(); ++it)
    cout << *it;

// 3. La boucle « pour chaque » : le compilateur écrit la 2 pour toi.
//    `const int&` plutôt que `int` — on ne copie pas pour lire.
for (const int& x : v)
    cout << x;

La condition d'arrêt est it != v.end(), jamais it < v.end() : l'itérateur d'une liste chaînée ne sait pas se comparer par ordre, seulement par égalité.

Un mot sur end(), parce que c'est la source d'erreur numéro un de la STL. v.end() ne désigne pas le dernier élément : il désigne la position juste après le dernier. C'est une borne, pas un élément — une sentinelle. Le dessin mental correct est celui d'une règle graduée : les éléments sont entre les graduations, et end() est la dernière graduation, celle qui ferme. Elle sert à savoir qu'on est arrivé, et à rien d'autre.

Deux conséquences immédiates. *v.end() est un comportement indéfini : il n'y a rien à cet endroit. Et pour obtenir le dernier élément, il existe une méthode faite pour ça, v.back() — c'est elle qu'on emploie, pas une arithmétique sur end().

Un dernier couple à connaître, parce qu'il tombe régulièrement à l'examen : pour lire l'élément d'indice i d'un vector, deux écritures existent. v[i] ne vérifie rien — si i est hors des bornes, tu lis la mémoire du voisin, sans message. v.at(i) vérifie et lance une exception si l'indice est invalide. La seconde est plus sûre, la première est plus rapide ; le cours emploie les deux, et ce qu'on te demande, c'est de savoir laquelle protège.

vector<int> v = {10, 20, 30};

for (auto it = v.begin(); it != v.end(); ++it)
    cout << *it;

cout << *v.end();     // affiche 30 ?

Le TAD : le quoi, et le comment

Ce module s'achève sur une idée qui n'est pas du C++ du tout, et qui gouverne pourtant tout le reste de la session. Elle tient en une distinction : ce qu'une structure permet de faire n'est pas la même chose que la façon dont elle est faite.

Quand tu demandes une pile, ce qui t'intéresse est : puis-je empiler, dépiler, regarder le sommet, savoir si elle est vide ? La réponse à ces quatre questions ne change pas selon qu'elle est construite avec un tableau ou avec une liste chaînée. Cette description — les opérations, et ce qu'elles promettent, sans un mot sur leur réalisation — s'appelle un type abstrait de données, ou TAD.

L'intérêt n'est pas philosophique : il est très concret. Si deux implémentations respectent le même TAD, on peut les échanger sans toucher une ligne du code qui s'en sert. Ce qui change alors n'est pas ce que le programme fait, c'est ce qu'il coûte — et c'est précisément l'objet du cours. Le tableau ci-dessous est la carte de la session entière : à gauche les TAD, à droite les implémentations qu'on va étudier une par une.

La question « quelle est la différence entre un TAD et son implémentation ? » est de celles qui tombent à l'examen, et une bonne réponse tient en trois temps qu'il vaut mieux avoir en tête que d'improviser. Un : énoncer la distinction — le TAD décrit les opérations et leur contrat, l'implémentation décrit la structure interne qui les réalise. Deux : donner un exemple concret avec deux implémentations du même TAD — une pile faite avec un tableau, une pile faite avec une liste chaînée. Trois : dire ce que le choix change, et c'est ce troisième temps qui rapporte les points — il ne change pas l'interface, il change les complexités et l'occupation mémoire.

C'est aussi l'annonce du module suivant. On vient de faire le tour des outils ; Les structures linéaires prend chacun des TAD de ce tableau et l'implémente pour de bon, en mesurant ce que chaque choix coûte.