Big Tuto : Apprenez le C++

Chapitre 24 : Conteneurs séquentiels et conteneurs adaptatifs (3)

Tutoriel présenté par : Robert Gillard (Gondulzac)
Date de publication : 6 octobre 2017
Date de révision : -

Retrouvez les projets complets de ce chapitre :

   Préliminaires

   Nous poursuivons notre étude des conteneurs séquentiels avec la suite des opérations STL sur le conteneur ''String''.

   La seconde partie de ce chapitre sera consacrée à la découverte de trois nouveaux conteneurs séquentiels dénommés conteneurs adaptatifs. 

  1.0 – Opérations STL sur le conteneur ''string'' (suite)

   1.1 – Les fonctions append() et replace()

   Lorsque nous faisons des concaténations de chaînes telles

   maChaine = maChaine + autreChaine;
   machaine += autreChaine;

   nous savons maintenant que la classe string utilise ses propres opérateurs surchargés std::string::operator+, std::string::operator= ou std::string::operator+= pour réaliser de telles opérations.

   Il se fait que la classe string définit également deux membres additionnels, append et replace, qui respectivement peuvent ajouter des éléments en fin de chaîne ou remplacer des éléments à l'intérieur d'une chaîne.

   L'opération replace a ceci d'intéressant qu'elle remplace à elle seule les deux opérations erase et insert.

   Nous allons voir une utilisation de ces deux fonctions dans un simple exemple  :

   Projet 140ContSequentiels_9 

   Notons que dans l'instruction chaine5.erase(27, 20), le premier paramètre de la fonction erase() est la position du premier caractère devant être supprimé. Le second paramètre est la longueur du tableau const char *tab.

   Dans chaine5.insert(27, chaine4), chaine4 étant une variable de type string, nous pouvons mettre son nom comme second paramètre.

   La fonction replace() possède trois paramètres, le premier étant toujours la position à partir de laquelle le premier élément doit être supprimé. Le second paramètre la suite d'éléments qui doivent être remplacés et le troisième paramètre les nouveaux éléments.

   Notez que le second paramètre étant ici le nom de la chaîne, sa longueur doit impérativement être connue par la fonction d'où l'expression chaine4.size().

   Ce qui donne comme résultat dans la console :

   1.2 – Opérations de recherche sur les chaînes

    La classe string contient six fonctions membres STL dont une nommée find(). Chacune des opérations de recherche effectuée avec find() retourne une valeur de type std::string::size_type.

   Cette valeur est l'index du premier élément trouvé. Si la recherche ne donne aucun résultat, la fonction retourne un membre statique dénommé string::npos. La bibliothèque string définit npos comme étant de type const string::size_type, initialisé à la valeur -1.

   Comme npos est un type non signé, ce membre statique est alors considéré comme étant égal à la plus grande taille possible qu'une chaîne peut emmagasiner. 

   Nous allons présenter un exemple de recherche d'une sous-chaîne ainsi que le nombre d'occurrences d'un certain élément (caractère) dans une chaîne. Cela va certainement vous faire penser au projet 063VectorFunc_2 du chapitre 9, à part qu'ici nous utiliserons la fonction STL find(). 

   Exemple :

      Projet 141ContSequentiels_10 

   Notre programme est découpé en 3 parties.

   Dans la première nous recherchons la sous-chaîne 'roi' dans la chaîne 'Nabuchodonosor roi de Babylone'.

   Nous initialisons premièrement à 0 une variable ''debut'' de type size_t. Cette variable, passée comme second paramètre à la fonction find(), indique simplement le numéro d'index de début sur lequel doit s'effectuer la recherche. Et comme cette recherche s'effectue tout naturellement en position 0, cet index est égal à 0.

   La variable position de type auto retournera quant-à-elle la position dans la chaîne où la sous-chaîne 'roi' aura été trouvée par la fonction find().

   La variable ''nb_occurrences'' nous donnera le nombre de fois que la sous-chaîne 'roi' aura été trouvée.

   Dans la seconde partie nous initialisons ensuite une seconde chaîne où la sous-chaîne 'roi' se retrouve deux fois. Nous parcourons alors la chaîne à l'aide d'une boucle while tant que tous les numéros d'index n'ont pas été testés. Ceci nous oblige à repositionner la variable début sur l'index où nous trouverons la sous-chaîne suivante en assignant à ''debut'' la valeur de ''position + 1''.

   Dans la troisième partie, nous faisons la même opération que ci-dessus en passant en premier paramètre à la fonction find() la variable ''caract'' représentant le caractère 'o' à rechercher. Les variables ''position'' et ''nb_occurrences'' nous donnant de même les positions des caractères trouvés ainsi que le nombre de ceux-ci. 

   Et ceci nous donne comme résultat dans la console :  

   Et cet exercice nous amène déjà à un petit challenge ! 

  Exercice 1 (un petit challenge)

   Ecrivez un programme qui contiendra les fonctions Recherche_mot() et Recherche_char().

   Les recherches identiques à celles de notre exemple se porteront sur la chaîne ''Le grand roi Nabuchodonosor, roi de Babylone''.

   Dans les fonctions à écrire vous utiliserez cette fois la fonction STL find() de la classe string. Les positions du mot 'roi' et des caractères 'o' seront placés dans une référence vers deux conteneurs séquentiels autres que vector, deux conteneurs deque par exemple. Le contenu de ceux-ci sera affiché dans la fonction main().

   Quelques exemples : 

   Ici, pos affichera 0. Il s'agit de l'index où la sous-chaîne ''Gondul'' sera trouvée dans ''Gondulzak''.

   Cet autre exemple vous montrera le problème que l'on peut rencontrer avec les majuscules et les minuscules. En effet, si par exemple la chaîne dans laquelle la recherche se fait est écrite ''gondulzak'' et que l'on recherche la sous-chaîne ''Gondul'', la fonction find() ne trouvera pas la sous-chaîne et retournera le membre statique string::npos.

   Quelquefois il est plus intéressant de chercher la position du premier caractère qui ne se trouve pas dans une sous-chaîne. Supposons par exemple la recherche de la valeur numérique ''0'' dans la sous-chaîne ''G0ndul''.

   Ici, pos aura la valeur 1. Cette valeur est bien celle de l'index de la valeur numérique ''0'' dans la sous-chaîne ''G0ndul''. 

   1.3 – Spécifier où commencer une recherche

   Nous pouvons bien entendu commencer une recherche à une valeur d'index que nous aurons choisie. Si celle-ci n'est pas spécifiée, la recherche commencera à l'index 0.

   Supposons par exemple que nous désirions retrouver les indices d'une formule quelconque par rapport à une liste de chiffres :

   La condition de la boucle while réinitialise la variable pos à l'index du premier chiffre rencontré à partir de la valeur courante de pos. Chaque fois que la fonction find_first_of() retourne un index valide, on affiche le résultat courant et on incrémente pos.

   Ce qui donne dans la console :

   1.4 – Recherche de la dernière position d'une sous-chaîne

   La fonction find() que nous avons utilisée jusqu'à présent s'exécute de la gauche vers la droite.

   La bibliothèque string permet également une opération analogue utilisant la fonction rfind(), mais qui s'exécutera de la droite vers la gauche.

   Si nous reprenons notre chaîne de l'exemple précédent : ''Le grand roi Nabuchodonosor, roi de Babylone'', la fonctions rfind() recherchera la dernière position de la sous-chaîne ''roi'' :

    Ce qui donne 29 comme valeur de derniere_pos.

   1.5 – La fonction ''compare()''

   En complément aux comparaisons de chaînes à l'aide des opérateurs relationnels (voir chapitre 5 - § 1.2 – La classe ''string'' de C++ , ''Autres exemples d'opérations sur les chaînes''), la bibliothèque ''string'' nous procure des fonctions de comparaison similaires à la fonction ''strcmp'' de la bibliothèque C. De la même manière que ''strcmp'', la fonction ''chaine.compare(chaine2)'' retourne les valeurs 0, 1 ou -1 selon que ''chaine'' est égale, plus grande ou plus petite que chaine2. 

   Un petit exemple :

   Soit à comparer les deux chaînes suivantes :

''Assourbanipal''
''Jeremie''

   Heu... ne confondez pas hein, il s'agit bien de Jay81 notre Grand Administrateur, pas le prophète !  

   Projet 142ContSequentiels_11   

   Selon un certain nombres d'arguments qui lui sont passés, la fonction compare peut s'écrire de plusieurs manières différentes. Nous présentons ici les trois principales écritures.

      Et nous présentons un simple exemple de ces différentes écritures de la fonction compare().

      Dans l'exemple précédent nous avons vu la première manière d'écrire de la fonction, nous passons donc à la seconde.

    chaine1.compare(pos1, n1, chaine2) :

   Nous comparons la chaîne ''Meruvia'' de ch1 à la chaîne ch2. Dans ch1, ''Meruvia'' est située à l'index pos1 = 11 et comporte 7 caractères.

   La valeur de result est 0, ce qui veut dire que les chaînes sont identiques. 

    chaine1.compare(pos1, n1, pos2, n2, chaine2) :

   Ici, nous allons comparer les sous-chaînes ''end'' dans ch1 et ch2

   Dans ch1, ''end'' se trouve à l'index 3 et contient 3 caractères. Dans ch2, ''end'' se trouve à l'index 16 et contient 3 caractères.

   La valeur de result est 0, les sous-chaînes sont donc identiques. 

   1.6 – Conversions numériques

   Quelquefois, une chaîne peut contenir une sous-chaîne ou être elle-même une suite de caractères représentant un nombre. Le nouveau standard C++ a introduit une série de fonctions de conversion de caractères en nombre et, vice-versa, de nombre en chaîne.

   Quelques exemples :

   Transforme val en chaîne. L'affichage donnera 128.

   Transforme la chaîne ''128'' en valeur 128 de type double.

   Conteneurs séquentiels adaptatifs

         1.0 – Généralités

   En complément aux conteneurs séquentiels, la bibliothèque définit trois conteneurs séquentiels adaptatifs (adaptateurs). Ceux-ci sont dénommés stack, queue, et priority_queue. Un adaptateur est un mécanisme permettant à un élément d'agir comme un autre le ferait.

   Par exemple, l'adaptateur stack utilisera un conteneur séquentiel autre que array ou forward_list pour réaliser des opérations comme une pile LIFO.

   Nous verrons un peu plus loin la manière de fonctionner d'un adaptateur stack mais nous allons auparavant présenter les opérations communes pouvant être réalisées sur les différents conteneurs adaptatifs ainsi que comment définir un adaptateur.

      1.1 – Définir un adaptateur

   Un adaptateur définit deux constructeurs. Le constructeur par défaut crée un objet vide et le second constructeur utilise un conteneur compatible qui initialise l'adaptateur en copiant le conteneur utilisé.

   Exemple :

   Soit un conteneur deque<int> myInts;

   Nous pouvons utiliser myInts pour initialiser une nouvelle pile comme ceci :

stack<int> myStack(myInts);         //ok car types identiques <int>.

   Nous pouvons surcharger le type du conteneur par défaut en nommant un conteneur séquentiel comme argument d'un second type lorsque l'on crée l'adaptateur.

   Exemple :

Choix d'un conteneur pour un adaptateur donné

Tous les conteneurs ne peuvent pas être utilisés avec un adaptateur donné. Chaque adaptateur doit avoir la possibilité d'ajouter ou de supprimer des éléments et nous pouvons déjà exclure le conteneur array.

D'autre part, nous ne pouvons pas non plus utiliser le conteneur forward_list car tous les adaptateurs nécessitent de pouvoir ajouter, supprimer ou accéder au dernier élément d'un conteneur.

L'adaptateur stack n'a besoin que d'utiliser les opérations push_back, pop_back ou back de telle manière que nous ne pouvons pas utiliser d'autres opérations sur une pile. L'adaptateur queue, quant-à-lui accessible par le début et par la fin, utilisera les opérations back, push_back, front et push_front, ceci lui permettant l'utilisation des conteneurs list et deque, à l'exception de vector.

L'adaptateur priority_queue permet l'accès aléatoire en plus des opérations front, push_back et pop_back, de telle manière qu'il peut être utilisé avec les conteneurs vector ou deque, à l'exclusion de list.
 

      1.2 – L'adaptateur ''stack''

   L'adaptateur (ou conteneur adaptatif) stack est défini dans le fichier header <stack>, dans l'espace de nom std et est implémenté à la façon d'une pile LIFO. De tous les éléments d'une pile, le dernier stocké sera le premier enlevé. Le dessus de la pile est appelé le sommet et les opérations d'ajout et de suppression sont appelées respectivement empiler et dépiler (push et pop).

   Remarquez que dans un adaptateur, de la même manière que dans un conteneur, les éléments stockés doivent impérativement être de même type.

Empiler (push)           Dépiler (pop)                          

   Dans une pile LIFO, l'élément 1 est d'abord déposé. Les élément 2, 3, 4, jusque n sont ensuite respectivement empilés dans cet ordre.

   Dans notre schéma, l'élément n est déposé en dernier. Ces éléments seront enlevés (dépilés) dans l'ordre inverse, l'élément n étant enlevé le premier, puis l'élément n-1, et ainsi de suite jusqu'à
l'élément 1. Le dernier élément empilé sera donc le premier enlevé de la pile (Last In First Out ou LIFO en termes anglo-saxons).

   Nous allons montrer dans un simple exemple, un programme qui illustre l'utilisation d'un adaptateur stack.

   Exemple :

      Projet 143ContAdaptatifs_1 

   Et nous n'oublions pas d'inclure le fichier header <stack> au début de notre projet sinon nous ne pourrions pas compiler. 

   Dans la fonction main(), nous initialisons une pile vide ainsi qu'une variable entière à zéro.

   On remplit la pile avec les 15 premiers entiers (0… 14) et ensuite nous affichons ses éléments.

   Tant que la pile n'est pas vide, dans une boucle while, nous donnons à notre variable nombre la valeur de l'élément du dessus de la pile (top), nous l'affichons et le supprimons ensuite (pop).

   L'affichage des éléments se fait donc à partir du dernier élément empilé (14) jusqu'au dernier (0), (voir fonctionnement de l'adaptateur stack ci-dessus ).

   Attention : si vous avez besoin d'un élément de la pile pour une opération ultérieure, vous devrez nécessairement le sauver dans une variable avant de le supprimer ! 

   Le résultat dans la console :

   1.3 – L'adaptateur ''queue''

   L'adaptateur queue est défini dans le fichier header <queue>, dans l'espace de nom std et est implémenté à la façon d'une file FIFO. Nous insistons sur le fait que cet adaptateur n'agit pas comme une pile mais bien comme une file : imaginez un groupe de personnes attendant leur tour devant un guichet de cinéma. Il est clair que c'est la personne arrivée la première à ce guichet qui rejoindra la salle la première.  Cette façon de procéder est identique à une file FIFO (First in, First out). 

   De même que dans un adaptateur stack, les éléments stockés dans l'adaptateur queue doivent impérativement être de même type.

Entrée dans la file (push)                                                        

                                                   Sortie de la file (pop)

   Dans le schéma, l'élément 1 est le premier de la file et en sortira donc le premier.

   Nous allons montrer dans un simple exemple, un programme qui illustre l'utilisation d'un adaptateur queue. 

   Exemple :

      Projet 144ContAdaptatifs_2 

     Si vous avez bien lu les exemples de construction précédents, vous n'aurez aucune peine à comprendre ce programme. Au début de la fonction main() nous initialisons un tableau d'entiers représentant des dizaines (10...100) mais placées dans un ordre quelconque.

   Vous remarquerez que nous ne créons pas la priority_queue ''seconde_File'' avec tous les éléments du tableau mais uniquement avec les 5 premiers éléments, ceux-ci étant pris dans l'intervalle [mesEntiers, mesEntiers + 5], soit les nombres 10, 40, 70, 20, 50.

   Dans la priority_queue ''troisieme_File'', nous ajoutons une nouvelle valeur avec l'instruction

troisieme_File.push(35);

   Et vous vous apercevrez que lors de l'affichage, la file est automatiquement triée. 

   Ce qui donne comme résultat dans la console :

   Organiser ses priorités
 

   Bien, retournons quelque peu en arrière et penchons nous sur l'exemple qui a affiché dans l'ordre Wiwi, Rabidja, Arwel et Aron.

   Cet affichage est dans un ordre tout à fait normal car nous savons maintenant comment la classe string recherche la plus grande de deux chaînes (voir chapitre 5, § 1.2, ''Autres exemples d'opérations sur les chaînes'').

   Cependant, certains d'entre-vous vont me dire ''Oui mais moi je voudrais organiser mes priorités comme bon me semble, est-ce possible ?''. 

   Et bien oui, c'est possible, et nous allons voir comment. Il nous faudra cependant quelque peu empiéter sur la suite du cours mais c'est très facile à comprendre. 

   Allez, nous allons ajouter Roswyn à nos quatre personnages, la pauvre est bien seule et doit beaucoup s'ennuyer, maintenant... 

   Supposons que nous décidions, que lors de l'affichage de nos chaînes, nous ayons ceci comme affichage, avec Roswyn en priorité la plus haute afin qu'elle soit la première de la file :

   Nous allons montrer comment faire avec un exemple que nous écrirons dans un seul fichier.

   Toutes les explications nécessaires suivront par la suite. 

   Projet 146ContAdaptatifs_4 

      Notre programme débute avec une structure de type Personne. Nous y intégrons une variable de type string et une autre de type int, représentant respectivement les nom et priorité d'un objet à créer.

   Nous définissons également le constructeur de Personne à l'intérieur de la structure, constructeur prenant nos deux variables en paramètres.

   La classe ''Comparaison'' qui suit va sans doute vous interpeller. En effet, la remarque qui la précède indique ''Foncteur de comparaison'', mais que ceci ne vous perturbe pas. Nous approfondirons plus tard le rôle des foncteurs mais retenez dès à présent qu'un foncteur est un objet qui se comporte comme une fonction. Il s'agit en réalité d'une classe qui redéfinit notamment l'opérateur operator() comme dans notre exemple. Ici, la fonction operator() prend en paramètres deux références sur des objets de type Personne et compare leur priorités.

   Au début de la fonction main(), nous créons cinq objets en leur passant en paramètres la priorité désirée ainsi que le nom associé à cette priorité.

   A la ligne suivante, le constructeur surchargé de l'adaptateur priority_queue prend un paramètre supplémentaire qui n'est autre que notre foncteur Comparaison.

   Les éléments sont alors stockés dans la file dans un ordre quelconque et sont ensuite récupérés dans la boucle while avec la priorité que nous avons nous-même fixée. 

   Ce qui affiche dans la console :

   Allez, pourquoi pas un second challenge ? 

   Exercice 2 (Un second challenge)

   Ecrivez un programme en reprenant les 9 objets de type ''Arme'' de la fonction main() du projet 138ContSequentiels_7 du chapitre 23.

   Après avoir créé les 9 objets en fonction du prix croissant, vous créerez une priority_queue dans laquelle les objets seront stockés dans un ordre quelconque.

   Pour terminer, vous afficherez tous les éléments de la file selon une priorité désirée du plus cher vers le moins cher.

   Vous utiliserez le foncteur de comparaison de l'exemple précédent et vous devrez ajouter 2 fonctions au programme car ce sont des objets que vous allez afficher cette fois, pas des chaînes, donc... 

   2.0 Corrigé de l'exercice du chapitre 23

   Un petit challenge :

   Pour cet exercice on demandait : Ecrivez un programme dans lequel vous créerez une forward_list contenant des unsigned int de 1à 15. Affichez la liste et recherchez tous les éléments impairs que vous supprimerez. Affichez à nouveau la liste modifiée.

   Le code : 

   Pour commencer, nous n'oublions pas d'inclure le header <forward_list> en début de programme. 

   Dans la fonction main(), on crée une forward_list d'unsigned int en l'initialisant avec des valeurs comprises entre 1 et 15.

   Nous avons dit que pour agir sur le premier élément d'une forward_list, nous devions pouvoir accéder à l'élément précédent ce premier élément. Nous créons donc un itérateur dénommé ''precedent'' qui pointe sur l'élément qui précède le premier de la liste. L'itérateur ''courant'' va pointer, quant-à-lui sur le premier élément de la liste.

   Dans une boucle while, nous allons premièrement afficher tous les éléments de la liste à l'aide de l'itérateur déréférencé *courant.

   Par la suite, nous allons supprimer tous les éléments impairs de la liste. A cet effet, nous testons l'itérateur déréférencé *courant et nous l'enlevons de la liste à l'aide de la méthode erase_after() s'il s'agit d'un élément impair, sinon on continue à tester en donnant à ''precedent'' la valeur de ''courant'' et en incrémentant ce dernier. 

   Ce qui affiche dans la console :

   Voilà, c'est tout en ce qui concerne ce chapitre. 

   Les corrigés des exercices de ce chapitre seront présentés à la fin du chapitre 25.

   @ bientôt pour le chapitre 25 - L'Héritage (1).                                                                 

            Gondulzak.