• Nous avons conçu une pile de flottants. Si nous avons besoin d'une pile d'entiers, faut-il dupliquer le code en remplaçant double par long ? Et si nous avons besoin d'une pile de chaînes de caractères ?
• La généricité est un mécanisme permettant de définir un modèle de classe en laissant non défini certaines caractéristiques (nommées paramètres de généricité), ici le type des éléments stockés dans la pile.
• On peut alors instancier ce modèle de classe, en fixant les paramètres de généricité, pour obtenir une classe instanciable.

• La syntaxe C++ utilise le mot clef template.
• Pour l'exemple de notre classe Pile, on remplace dans le code le type actuel des éléments (double) par un paramètre de généricité (souvent noté T, mais c'est simplement un identificateur).
• Les paramètres de généricité (il n'y en a qu'un seul dans notre exemple) sont listés entre les caractères < et >.
• En C++, un paramètre de généricité n'est pas obligatoirement un type (voir plus loin). Initialement, le mot clef class a été retenu pour indiquer que T est ici un paramètre de généricité de sorte type (mais ce n'est pas obligatoirement une classe, un type primitif pourra être utilisé), ceci afin d'éviter d'avoir à ajouter un nouveau mot clef. Par la suite, le mot clef typename a été ajouté pour lever certaines ambiguïtés dans la grammaire du langage.
• Pour la définition des méthodes, il faut préciser qu'elles concernent un modèle de classe Pile< T >, et non une simple classe Pile.

• Pour instancier un modèle de classe, le compilateur C++ doit bien sûr connaître sa définition. Les méthodes ne sont réellement compilées que lors de l'instanciation du modèle de classe, c'est pourquoi elles figurent en général aussi dans le fichier d'entête.
• Le compilateur vérifie cependant la bonne syntaxe de la définition du modèle de classe.

• Pour instancier un modèle de classe, il suffit de fixer le ou les paramètres de généricité.
• Chaque instanciation avec un type différent crée un nouveau type, et le compilateur réalise bien sûr les vérifications nécessaires.

• Ce fichier dans le dépôt Git montre cette version générique de notre classe Pile.

• Un paramètre de généricité est le plus souvent un type. Il est aussi possible qu'un paramètre de généricité soit une valeur discrète (donc pas de flottants).
• Nous pouvons par exemple faire le choix de conception que la taille d'une pile est fixe et connue à la compilation ; cette taille peut donc être un paramètre de généricité.
• Cette version a comme avantages :
  • l'attribut taille_ est inutile,
  • il n'y a pas d'allocation dynamique du tableau,
  • les 4 comportements utilitaires générés sont corrects SI ceux du type T sont corrects.
• Par contre, la taille faisant partie du type, un tableau de 10 entiers n'est pas du même type qu'un tableau de 11 entiers.
• Il est possible de donner une valeur par défaut à des paramètres de généricité.

• Ce fichier dans le dépôt Git montre cette version générique de notre classe Pile.

• Il est aussi possible de définir des modèles de fonction.
• Pour obtenir l'équivalent en C (version générique par rapport aux types, pas de surcoût de l'appel d'une fonction), on utilise habituellement une macro.
• La version C++ ne fait pas de double évaluation d'un des arguments, gère les éventuels effets de bord... et s'utilise aussi facilement (déduction par le compilateur du paramètre de généricité).

• Il est possible de donner une version spécifique d'un modèle de fonction (ou d'un modèle de classe) qui sera utilisé à la place de la version générique.
• Une spécialisation peut être partielle.

• De même, il est possible de définir des modèles de méthode (dans une classe normale ou dans un modèle de classe).

• Ce fichier dans le dépôt Git montre cette version générique améliorée de notre classe Pile.

• On a montré que la partie généricité du langage C++ est équivalent à une machine de Turing.
• On peut donc calculer ce qui est calculable à la compilation, on parle de méta-programmation, méta-fonction…
• Cette partie n'a aucun effet de bord, elle est purement fonctionnelle.

• Ce fichier dans le dépôt Git montre ce calcul de factorielle via la méta-programmation.

• En informatique le polymorphisme est l'utilisation d'un même code avec différents types, ce qui permet des implémentations plus abstraites et générales.
  • Universel : le code peut être utilisé avec différents types
    • Héritage : la liaison dynamique permet d'exécuter la méthode appartenant au type de l'objet au moment de l'exécution et non à son type au moment de la compilation.
    • Paramétrique : au moins l'un des types n'est pas spécifié lors de la définition, il est précisé lors de l'utilisation.
  • Ad Hoc : le compilateur adapte le code généré en fonction des types utilisés (facilité d’écriture) :
    • Surcharge : le compilateur traduit un + par une addition entière avec des int, une addition flottante avec des double, une concaténation avec des std::string…
    • Conversion : le compilateur insère une conversion entier vers flottant quand il doit ajouter un int et un double.

• Lien vers la page Wikipédia sur la STL

• Pour comprendre la philosophie de la STL, il faut repartir du langage C.
• Nous prenons comme exemple de départ un besoin d'initialiser à 1 tous les éléments d'un conteneur.
• Dans ce langage, le seul conteneur standard est le tableau basique.
• On peut le parcourir avec un indice, mais cette méthode suppose un accès direct à n'importe quel élément d'un conteneur ; ce n'est donc pas généralisable à d'autres sortes de conteneurs.

• Cependant, on peut aussi parcourir un tableau basique avec un pointeur.
• On utilise ici un accès séquentiel qui est beaucoup plus général.
• On nomme itérateur un objet permettant de parcourir un conteneur.
• La lecture de la version C met en évidence les besoins et syntaxe suivants :
  • un conteneur doit être en mesure de fournir un itérateur permettant d'accéder à son premier élément ;
  • un conteneur doit aussi fournir un itérateur sur l'après-dernier élément : on peut l'utiliser pour comparer, mais on ne doit pas l'utiliser pour accéder à un élément ;
  • quand on a un itérateur, l'opérateur * permet d'accéder en lecture et en écriture à l'élément sous-jacent dans le conteneur ;
  • l'opérateur ++ permet de faire progresser l'itérateur vers l'élément suivant.

• On retrouve ces concepts dans la STL :
  • l'un des tableaux proposés par cette bibliothèque est std::vector, il est bien sûr générique par rapport au type des éléments stockés ;
  • un conteneur de la STL doit fournir un type, iterator, permettant de définir un itérateur sur ses éléments ;
  • un conteneur de la STL doit fournir une méthode, begin(), retournant un itérateur pointant sur son premier élément ;
  • un conteneur de la STL doit fournir une méthode, end(), retournant un itérateur pointant sur son après-dernier élément ;
  • quand on a un itérateur, l'opérateur * permet d'accéder en lecture et en écriture à l'élément sous-jacent dans le conteneur ;
  • l'opérateur ++ permet de faire progresser l'itérateur vers l'élément suivant.
• Ce code serait identique avec un autre type de conteneur de la STL (en remplaçant vector par cet autre type).

• Il est important d'utiliser ici des parenthèses pour obtenir un tableau de taille 10.
• En effet, l'écriture

std::vector< int > tab{ 10 };

std::vector< int > tab{ 1, 2, 3, 4, 5 };

• On note ici l'intérêt du typage par inférence : l'obligation de donner explicitement le type de l'itérateur n'est pas justifiée.
• L'utilisation des fonctions libres std::begin() et std::end() permet d'avoir un code plus général, qui marche par exemple avec des tableaux basiques.

• Il existe un for spécifique qui est traduit par le compilateur en des appels à std::begin() et std::end(), avec un accès direct à l'élément sous-jacent à l'itérateur.
• L'accès en écriture impose par contre l'utilisation de la référence sur valeur gauche.

• On peut souhaiter créer un service de mise à 1 de tous les éléments d'un conteneur quelconque.
• Cela revient à créer un modèle de fonction générique par rapport au type du conteneur.

• Le service modifiant tout le conteneur peut sembler pas assez général car ne permettant pas de travailler sur une partie d'un conteneur.
• Les algorithmes de la STL vont donc plutôt prendre comme argument une partie d'un conteneur identifiée par un itérateur sur le premier élément de cette partie et un autre sur l'après-dernier élément de cette même partie.
• L'algorithme est donc générique par rapport au type d'itérateur.

• Pour éliminer la restriction sur la valeur 1, il suffit de rajouter comme argument au modèle de fonction la valeur d'initialisation.

• Pour généraliser encore, et ne pas se limiter à de l'initialisation, on peut souhaiter appliquer un certain comportement fonctionnel aux éléments d'une partie d'un conteneur.
• Il faut que l'appel de ce comportement soit syntaxiquement correct pour le compilateur C++, c'est la cas avec un pointeur de fonction.

• Grace à la surcharge des opérateurs (qui sera vue plus tard), il est possible de créer des objets qui s'utilisent comme des fonctions (on les appelle des objets fonctions).
• Un tel objet peut donc être utilisé par notre algorithme.
• L'avantage est qu'un objet a un état qui reste accessible tant que l'objet existe, et qui peut être modifié lors du parcours.
• On peut par exemple imaginer un objet fonction qui mémorisera la somme des éléments lors du parcours.

• Ce fichier dans le dépôt Git montre les différents codes des précédents transparents.

• Le standard C++ n'impose par une implémentation particulière pour les conteneurs de la bibliothèque standard : ceux-ci sont spécifiés en terme de services offerts et de compléxité en temps des différentes opérations. Dans la pratique, cela ne laisse pas beaucoup de liberté sur la structure de données sous-jacente.
• Il existe 2 familles de conteneurs :
  • les conteneurs séquentiels stockent leurs éléments de façon strictement linéaire,
  • les conteneurs associatifs permettent l'accès rapide à leurs éléments à partir de clefs.
• Conteneurs séquentiels :
  • vector est le conteneur séquentiel à utiliser par défaut, il utilise un tableau basique en interne. Il n'y a pas de vérification de la validité de l'indice quand on accède aux éléments avec les crochets ([]) pour l'habituelle raison « Pay only for what you use ». La méthode at() propose si besoin cette vérification.
  • array est comme vector, mais avec une taille fixe (paramètre de généricité).
  • deque est en général réalisé sous la forme d'un tableau de (pointeurs sur) tableaux, il offre comme vector un accès direct en temps constant (mais légèrement moins bon), mais contrairement à ce dernier, l'insertion au début se fait aussi avec une compléxité constante (elle est linéaire pour vector).
  • forward_list est une liste simplement chainée, list est doublement chainée.
• Un premier groupe de conteneurs associatifs nécessite des clefs pouvant être comparées et offre des accès avec une compléxité logarithmique ; en pratique, ils sont réalisés avec des arbres bicolores :
  • map est un dictionnaire (permet d'associer une valeur à une clef),
  • set est un ensemble (pas de valeurs associées au clefs),
  • multimap permet d'avoir plusieurs valeurs associées à une même clef,
  • multiset permet qu'une clef soit présente plusieurs fois.
• L'autre gropue de conteneurs associatifs utilise des tables de hachage, on retrouve les 4 variantes décrites précédemment : unordered_map, unordered_set, unordered_multimap et unordered_multiset.
• On peut s'étonner de ne pas avoir un conteneur offrant un service de pile ; ce service est en fait proposé sous la forme d'un adaptateur, stack, qui laisse libre le choix du conteneur séquentiel sous-jacent. Avec le même principe, on trouve aussi un service de file (queue) et un autre de file avec priorité (priority_queue).

• Les conteneurs et itérateurs de la bibliothèque standard respectent un protocole commun qui inclut un ensemble de types et de méthodes.
• Il est possible de définir de nouveaux conteneurs et de les utiliser avec les algorithmes standards si ce protocole est respecté.

* Nous avons vu les 2 opérations de base d'un itérateur : * pour accéder à l'élément sous-jacent, ++ pour faire progresser l'itérateur. Selon le conteneur parcouru, d'autres possibilités existent ; par exemple, dans un vector, il est possible de faire reculer l'itérateur.

• Pour tenir compte de ces variantes, les itérateurs sont classés par catégories :
  • un forward_iterator est un type concret (en particulier pour les comportements de copie), et supporte ++ (en préfixé et postfixé) et * ; un itérateur de cette catégorie est retourné par forward_list et les conteneurs basés sur une table de hachage.
  • un bidirectionnal_iterator est un un forward_iterator supportant en plus -- (en préfixé et postfixé) ; un itérateur de cette catégorie est retourné par list.
  • un random_access_iterator est un un bidirectionnal_iterator supportant en plus + n, - n et [n] (n étant un entier) ; un itérateur de cette catégorie est retourné par les autres conteneurs standards.
• Par ailleurs, deux catégories spécifiques permettent d'utiliser les flux d'entrée et de sortie comme des conteneurs (et donc d'utiliser les algorithmes standards sur les flux d'entrée/sortie) ; pour ces catégories, les opérations d'accès et de progression doivent alterner strictement :
  • un input_iterator ne donne qu'un accès en lecture,
  • un output_iterator ne donne qu'un accès en écriture.
• Enfin, des adaptateurs d'itérateurs permettent un parcours en sens inverse (avec au minimum un bidirectionnal_iterator) et l'insertion d'éléments au moment du parcours.

• Il existe de nombreux algorithmes dans la bibliothèque standard, en voici quelques uns.
• À noter que, depuis C++17, il est possible de spécifier pour certains une politique d'exécution permettant d'exploiter le parallélisme des processeurs actuels.

© 2023 CentraleSupélec