Big Tuto : Apprenez le C++

Chapitre 23 : Les conteneurs séquentiels (2)

Tutoriel présenté par : Robert Gillard (Gondulzac)
Date de publication : 31 août 2017
Date de révision : -

Retrouvez les projets complets de ce chapitre :

   Préliminaires

   Avec ce 23ème chapitre nous continuons notre découverte des conteneurs séquentiels. Le sujet étant relativement vaste mais aussi très important, nous l'écrirons sur trois chapitres afin que vous puissiez profiter d'un maximum d'éléments s'y rapportant. 

   Nous commençons immédiatement par la suite du paragraphe 8 du chapitre 22 (Suppression d'éléments dans les conteneurs séquentiels). 

1 – Opérations sur les conteneurs séquentiels (suppression d'éléments) - Suite :

   1.1 – Suppression d'éléments multiples

   Nous pouvons supprimer les éléments compris entre une paire d'itérateurs à l'aide de la fonction erase() en utilisant les membres begin et end du conteneur comme nous pouvons supprimer tous les éléments d'un conteneur avec la fonction clear().

   Voyons ceci avec un simple exemple dans lequel nous créons un conteneur ''vector'' de type double et un conteneur ''vector'' de type string.  

   Exemple : Projet 136ContSequentiels_5

   Dans ce fichier nous créons donc un vector de doubles et un vector de strings. Nous allons montrer deux manières de suppression d'éléments multiples dans un conteneur. 

   Après affichage du contenu de nos deux vectors, nous présentons la première manière d'effacer une suite d'éléments dans un conteneur.

   Nous ne voulons pas supprimer tous les éléments du vector ''val'' mais seulement une suite d'éléments quelconques. Nous choisissons de supprimer les éléments situés au-delà de la seconde position jusqu'à l'élément situé deux éléments avant la fin du vector ''val''. Ceci revient à dire que nous voulons conserver les deux premiers ainsi que les deux derniers éléments du vector. Nous savons que begin() retourne un itérateur sur le premier élément d'un vector et end() un autre sur le dernier plus un élément de ce vector.

   Les éléments à supprimer sont donc bien ceux compris entre begin() + 2 et end() - 2.

   L'instruction val.erase(val.begin() + 2, val.end() - 2) effacera ces éléments. 

   Avec erase(), nous pouvons également effacer tous les éléments d'un conteneur. Notre vector ''val'' ne possède plus que quatre éléments après avoir effectué l'opération ci-dessus. Maintenant que begin() est le premier élément du vector modifié et end() en est le dernier élément, l'instruction val.erase(val.begin(), val.end()) va supprimer les éléments restants du vector ''val''.

   La fonction clear(), effacera quant-à-elle, tous les éléments d'un conteneur séquentiel. Donc pour supprimer entièrement le vector ''armes'' nous écrivons simplement : armes.clear();

   d'où l'identité des deux fonctions :

conteneur.clear() <=> conteneur.erase(conteneur.begin(), conteneur.end() )

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

   2 – Opérations spéciales du conteneur forward_list

      2.1 – Accès à un élément

   Dans le chapitre 22, § 1.1 – Types de conteneurs séquentiels, nous avons vu que contrairement aux autres conteneurs séquentiels, nous ne pouvons accéder au conteneur forward_list que dans une seule direction, du début vers la fin du conteneur.

   Le conteneur forward_list, étant considéré comme une liste simplement liée, nous allons voir à l'aide d'une illustration ce qui se passe lorsqu'on enlève un élément de la liste.

 Elément 1              Elément 2             Elément 3                Elément 4               Elément 5

   Supposons que nous devions supprimer l'élément n°4. Nous allons avoir besoin d'accéder à l'élément n°3 pour mettre à jour un nouveau lien. En effet, après suppression, l'élément n°3 va maintenant devoir pointer sur l'élément n°5 dans la liste. 

   Ceci revient à dire que nous devons connaître l'emplacement de l'élément précédent l'élément à supprimer.

   Pour cette raison, l'insertion ou la suppression d'éléments dans une forward_list se fera toujours en opérant un changement à la suite d'un élément donné.

   Ces opérations se comporteront donc différemment des opérations effectuées sur les autres conteneurs séquentiels. Le conteneur séquentiel forward_list ne définira donc pas les opérations ''insert'', ''emplace'' ou ''erase'' mais utilisera d'autres membres dénommés ''insert_after'', ''emplace_after'' et ''erase_after''.

   Dans l'illustration ci-dessus, pour supprimer l'élément n°4, nous ferons appel à l'opération ''erase_after'' sur un itérateur positionné sur l'élément n°3. 

   Et si nous voulons supprimer le premier élément de la liste, alors ? 

   Dans ce cas, le conteneur forward_list ne peut pas supprimer un élément à partir du membre begin. Il définit à la place un membre nommé ''before_begin'' qui retournera un itérateur sur l'élément précédent le premier élément de la liste. 

      2.2 – Opérations d'insertion ou de suppression d'éléments dans une forward_list

   Exercice (Un petit challenge)

   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. 

   3 – Changer la taille d'un conteneur séquentiel

   Excepté le conteneur ''array'', nous pouvons modifier la taille d'un conteneur séquentiel. Cette taille peut-être agrandie ou rétrécie à l'aide de la fonction resize(). Cette fonction peut prendre un ou deux argument selon que l'on veuille ou non changer le type des éléments modifiant le conteneur.

   Quelques exemples :

   Soit une liste de 15 unsigned initialisés avec la valeur 5 :

list<uint> ulist (15, 5)

   ulist.resize(25)                  ajoute 10 élément de valeur 0 à la fin de la liste d'origine.
   ulist.resize(26, -5)             ajoute 1 élément de valeur -5 en fin de liste
   ulist.resize(10)                  supprime les 16 derniers éléments de la liste.

   4 – Gestion de la taille d'un vector

   Dans un vector, les éléments sont stockés les uns à la suite des autres. Ceci permet d'avoir un accès aléatoire rapide sur ce type de conteneur. 

   Etant donné que les éléments sont contigus dans le conteneur et que celui-ci peut-être rétréci ou agrandi à volonté, considérons le cas où nous voudrions ajouter un élément dans un conteneur de type vector ou string mais qu'il n'y ait plus de place pour ce nouvel élément.

  Nous savons que le conteneur ne peut pas juste ajouter cet élément n'importe où dans la mémoire puisque tous les éléments doivent être contigus. Il va donc s'ensuivre des opérations relativement pénalisantes pour une exécution rapide de la gestion de ce conteneur. En effet, le conteneur va devoir allouer un nouvel emplacement mémoire pour y transférer tous les éléments existants plus le nouvel élément à ajouter. En plus, il va devoir désallouer l'ancien emplacement mémoire. Si ces opérations doivent se répéter chaque fois que l'on ajoute un élément dans le vector, la performance de l'accès à ce conteneur va rapidement chuter. 

   A cet effet, les conteneurs vector et string nous fournissent des membres qui permettent à l'utilisateur d'interagir directement sur l'allocation mémoire. 

Remarques :

      capacity et reserve ne sont valides que pour les conteneurs vector et string.
      shrink_to_fit est valide pour les conteneurs vector, string et deque.

   Bien, ces fonctions de gestion de la taille d'un conteneur demandent quand-même quelques explications complémentaires. 

   L'opération reserve ne change pas le nombre d'éléments d'un conteneur, elle affecte seulement la quantité de mémoire que le conteneur va pré-allouer.

   Un appel à reserve() changera la capacité d'un vector seulement si l'espace requis excède la capacité actuelle.

   Si la taille désirée est supérieure à la capacité courante, la fonction reserve() allouera au minimum la même quantité que la valeur désirée mais l'allocation est souvent supérieure à celle-ci.    

   Si la taille désirée est inférieure ou égale à la capacité courante, la fonction reserve() sera ignorée.

   Il s'ensuit qu'après avoir appelé la fonction reserve(), la capacité sera soit plus grande soit égale à la valeur n passée à la fonction.

   De le même manière, la fonction resize() ne changera que le nombre d'élément d'un conteneur, pas sa capacité.

   Le standard C++ 11 a ajouté la fonction shrink_to_fit() pour demander à un conteneur vector, string ou deque, de pouvoir désallouer une quantité de mémoire non nécessaire. Le programme est cependant libre d'ignorer cette requête et il n'y a aucune garantie qu'un appel à shrink_to_fit() ne désalloue une quelconque quantité de mémoire excédentaire. 

      4.1 - Taille et capacité d'un vector

   Nous allons maintenant, à l'aide d'un exemple, mieux nous rendre compte des subtilités apportées par ces différentes fonctions.

   Exemple : Projet 137ContSequentiels_6 

   Quelques remarques importantes sur ce programme :

  Nous commençons par créer un vector vide ''uvec'' d'entiers non signés. Nous affichons ensuite sa taille et sa capacité et à ce moment, celles-ci sont bien entendu de 0 chacune.

  Nous ajoutons ensuite 20 éléments dans le vector. Sa taille passe donc à 20 et sa capacité devrait également être de 20 au minimum. Nous voyons que le conteneur étend la capacité de uvec à 28, ce qui est tout à fait possible car si la capacité doit au moins être égale à la taille d'un vector, elle peut cependant avoir une plus grande étendue.

   Nous réservons ensuite un espace additionnel pour avoir une capacité de 100 éléments dans le vector. uvec.reserve(100) porte la capacité du vector à 100 mais n'intervient pas dans sa taille qui reste actuellement de 20 éléments.

   On décide par la suite d'utiliser toute la capacité du vector en augmentant sa taille avec les éléments 21....100. 

   Les deux lignes suivantes procèdent à cette opération :

   En effet, tant que la capacité du vector n'est pas atteinte, la fonction push_back() ajoute à chaque tour de boucle un élément de valeur équivalente à la taille du vector, celui-ci étant bien entendu incrémenté d'une unité par tour. En fin de boucle notre vector uvec possède donc une taille et une capacité de 100 chacune.

   Par la suite nous désirons augmenter la taille du vector de 1 élément, bien que la capacité du vector soit à ce moment égal à sa taille (100). Nous allons donc maintenant nous trouver dans le cas cité plus haut où le conteneur va devoir allouer un nouvel emplacement mémoire pour y transférer tous les éléments existants plus le nouvel élément à ajouter, et en plus, il va devoir désallouer l'ancien emplacement mémoire. A la suite de quoi la taille du vector passe à 101 éléments, le conteneur étendant sa capacité à une valeur de 150 afin d'avoir une réserve supplémentaire. 

   Pour terminer, nous décidons de désallouer cette mémoire excédentaire à l'aide de la méthode shrink_to_fit(). Et comme, nous l'avons dit auparavant, bien que celle-ci soit tout à fait libre d'ignorer notre requête, elle ramène la capacité de uvec égale à sa taille, c'est-à-dire 101.

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

Remarque :

   Vous aurez noté que pour l'ajout de 20 éléments dans le vector uvec, nous avons utilisé le type size_type pour l'initialisation de la boucle. Nous en avons parlé dès le chapitre 7 quand nous l'avons associé à la classe ''string''. Dans le chapitre 7 nous disions:

''Il se fait que la classe ''string'' ainsi que d'autres types de librairies définissent un certain nombre de ce qu'on appelle des ''types compagnons'' ou ''companions types''. Le type size_type est l'un de ces types compagnons et pour pouvoir l'utiliser nous devons ajouter l'opérateur de résolution de portée pour signaler qu'il est défini dans la classe <string>''.

   Dans notre exemple ci-dessus, le conteneur n'est pas ''string'' mais ''vector'' d'où notre boucle :

   Ce petit rappel effectué, notez que nous aurions pu utiliser, comme nous en avons l'habitude maintenant, le spécificateur de type ''auto'' pour un résultat absolument identique et plus facile à implémenter. 

for (auto i = 0; i != 20; ++i)

   5 – Modification de champs dans des objets d'un vector d'objets

   Considérons l'objet suivant :

Arme arme_2("Arc de la fureur de Myin", "Arc long composite", 5, 900, 2.5, 220);

   Nous avons ici un objet dénommé ''arme_2'' et appartenant à la classe Arme. A l'intérieur des parenthèses, nous voyons que cet objet contient 6 champs :

- Le champ ''Nom''       contient ''Arc de la fureur de Myin''
- Le champ ''Type''       contient ''Arc long composite''
- Le champ ''Degats''   contient la valeur ''5''
- Le champ ''Etat''        contient la valeur ''900''
- Le champ ''Poids''     contient la valeur ''2.5''
- Le champ ''Prix''        contient la valeur ''220''

   Nous allons maintenant voir comment modifier certains de ces champs dans des objets rassemblés dans un vecteur d'objets de la classe Arme. Ceci nous sera très utile pour la réalisation d'un exercice commenté sur une gestion Achats/Ventes entre un avatar et un marchand que nous pourrions introduire dans un rpg.

   Nous allons créer 9 objets de type Arme dans un projet contenant 3 fichiers comme nous l'avons déjà fait plusieurs fois jusqu'ici.

   Voyons ceci à l'aide d'un exemple :

      Projet 138ContSequentiels_7

         Fichier : ContSequentiel_7.h 

   Dans le fichier header, à l'intérieur de la classe Arme, nous déclarons un constructeur, un constructeur de copie, le destructeur, les méthodes membres d'accès publique ainsi que les données membres privées.

   Ces dernières représentent respectivement, comme nous l'avons fait remarquer plus haut, les champs Nom, Type, Degats, Etat, Poids et Prix d'un objet de la classe Arme.

   A l'extérieur de la classe, nous définissons une fonction operator<< qui nous servira à afficher les objets dans la fonction mainFile() (Voir chapitre 20, § 1.1, ''Surcharge de l'opérateur '<<' de la classe ostream'').

   Fichier : ContSequentiel_7.cpp 

   Rien de spécial dans le fichier .cpp. Nous définissons les constructeurs et les méthodes membres déclarés dans le fichier ConSequentiels_7.h.

   Fichier : ContSeq_7MainFile.cpp

     6.2 – La fonction substr()

Exemple :     

      Si pos est omis, la copie se fera en position 0 par défaut. 

     Si le nombre de caractères à copier est omis, la chaîne entière sera copiée.

      6.3 – Modes d'accès aux caractères d'une chaîne de la STL

    Nous avons deux possibilités : ou bien utiliser nos bons vieux indices issus du C ou mieux, parcourir notre chaîne à l'aide d'itérateurs. 

   Voyons ceci à l'aide d'un exemple :

      Projet 139ContSequentiels_8   

     Et nous voyons le résultat de notre exemple dans la console :

      6.4 – Opérations additionnelles de modification de chaînes

    En complément des versions qui utilisent insert, erase ainsi que les itérateurs, la classe string nous procure également d'autres versions utilisant un index. Cet index désigne le nombre  d'éléments à supprimer à partir de la fin de chaîne ou donne l'élément et sa quantité à insérer en fin de chaîne. 

     La bibliothèque string procure également des versions de insert et assign qui se réfèrent à des tableaux de caractères de style-C.

     Et pour connaître le contenu des Légendes de Meruvia, demandez à … Roswyn !?

   7 – Corrigés des exercices du chapitre 22

      Exercice 1 ( projet Chap22Exercice_1)

   Dans cet exercice on demandait d'écrire un programme avec une fonction qui affiche la liste inversée des entiers du projet 132ContSequentiels_1 du chapitre 22. Utilisez le conteneur ''deque''.

   Le code :

   Nous déclarons premièrement une fonction Lis_liste() à laquelle on passe une référence sur un conteneur deque d'entiers en paramètre.

   Dans la fonction main(), nous initialisons un conteneur deque avec une série d'entiers quelconques.

   On appelle ensuite la fonction Lis_liste(). Dans celle-ci, nous affichons en premier la liste à l'endroit. Nous utilisons pour ce faire les fonctions STL begin() et end(). Remarquez à nouveau l'écriture concise utilisant le spécificateur de type auto pour l'initialisation des variables ''debut'' et ''fin''.

   Pour rappel :

      auto debut = begin(nombres) <=> deque<int>::iterator debut = begin(nombres)
      auto fin = end(nombres) <=> deque<int>::iterator fin = end(nombres)

   Pour la lecture de la liste à l'envers, nous utilisons les membres rbegin et rend qui retournent un itérateur du dernier vers le premier élément moins un du conteneur (voir chapitre 22 §4 – Les différentes versions des membres begin et end d'un conteneur).

   Et vous devriez obtenir quelque chose de ce genre dans la console :  

   Exercice 2 ( projet Chap22Exercice_2)

   Pour cet exercice on demandait : Ecrivez une fonction à qui l'on passe une référence sur une chaîne représentant un mot quelconque. Cette fonction devra mettre le mot au pluriel et heu... si vous vous en souvenez, vous ferez un test sur les mots qui forment leur pluriel avec un 'X'. 

   Pour les perfectionnistes, vous pouvez ajouter les cas où le mot possède déjà un 'S' ou un 'X' au singulier.

   Le code :

   Et voici le corrigé d'écriture d'une fonction de mise au pluriel d'un mot quelconque de type string.

   Après la déclaration de la fonction Pluriel() à laquelle on passe une référence sur une chaîne en paramètre, dans la fonction main() on vous demande d'entrer un mot d'au moins deux lettres.

   Ben oui, c'est quand-même un minimum pour former un pluriel, non ? 

   La fonction size() nous retourne la longueur du mot entré. Le nombre de caractères est affiché et nous appelons la fonction Pluriel() qui mettra notre mot au pluriel selon les différents critères que nous nous sommes fixés.

   Dans la fonction Pluriel(), nous commençons par créer une variable de type char qui prendra un ''x'' ou un ''s'' suivant les cas envisagés.

   Notre premier test porte sur le cas où il y a déjà soit un s soit un x à la fin du mot que nous avons entré. Le dernier caractère de la chaîne est trouvé par la fonction back() (Voir chapitre 22 § 7.8 - ''Accéder aux éléments d'un conteneur séquentiel'').

   Et dans ce cas nous affichons simplement le pluriel (qui est égal au mot au singulier). 

   Si le dernier caractère du mot n'est ni un s ni un x, nous faisons alors un test pour voir si notre mot forme son pluriel en x. Et ici nous nous devons nous rappeler quels sont ces mots et heu...  c'est déjà peut-être loin pour certains, tout ça... 

   Bien, si le mot entré est un de ceux de notre test, nous mettons alors le caractère 'x' dans la variable char_fin, sinon le mot entré ne peut plus former son pluriel qu'avec un s et nous mettons le
caractère 's' dans la variable char_fin.

   La fonction push_back() ajoute alors le caractère de fin dans la chaîne et le mot au pluriel est affiché.

   Avec quelques résultats dans la console :  

   Exercice 3 (un petit challenge)

   Pour cet exercice on demandait de créer deux listes de valeurs de type double. Pour la première, il fallait reprendre la liste du projet 135ContSequantiels_4 du chapitre 22 et une liste vide pour la seconde, soit : 

list<double> val = { 3.5, -2.1, -9.9, 6.7, 12.4, 21.6, -17.1, -11.3, 7.9, 1.8 };

   ainsi qu'une liste vide pour recevoir des nombres négatifs, soit :

list<double> neg;

   Vous devrez enlever les nombres négatifs de la liste ''val'' et les transférer dans la liste ''neg''.

   Utilisez la fonction emplace_back() pour créer la nouvelle liste ''neg'' plutôt que de faire une copie des éléments négatifs de ''val''.

   Affichez ensuite les deux listes.

   Le code : 

    Ok, rien de chinois là-dedans.  On parcourt la liste de valeurs de type double à l'aide d'un itérateur de begin(val) à end(val) – 1 et on affiche ces valeurs.

   On initialise enuite deux autres itérateurs, iter2 et iter3, tous deux positionnés sur val.begin().

   Iter2 va parcourir toute la liste et lorsque le premier élément négatif sera trouvé, iter3 prendra alors la position de iter2 . La fonction emplace_back() crée et ajoute l'élément négatif dans la liste neg, soit l'itérateur déréférencé *iter3.

   L'élément négatif trouvé est alors supprimé de la liste val. Si l'élément pointé n'est pas un nombre négatif on incrémente alors iter2 et on continue à boucler.

   Pour terminer, on affiche les deux listes.

   Et ceci nous donne dans la console :

   Et 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 24.

      @ bientôt pour le chapitre 24 – Conteneurs séquentiels et conteneurs adaptatifs (3).                                                                     

            Gondulzak.