French Chinese (Simplified) Dutch English German Greek Italian Japanese Korean Spanish

     

 



 

   

 

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. wink



  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 wink :

 

   Projet 140ContSequentiels_9 

 

//Projet 140ContSequentiels_9
//Utilisation des fonctions append() et replace()
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
 
int main()
{
 
string chaine1("Mon meilleur allie est un ");
string chaine2("Elfe ");
string chaine3("noir ");
 
cout << endl;
//Concaténations effectuées par les opérateurs de classe
cout << "Concatenation effectuee par les operateurs de classe :" << endl;
chaine1 = chaine1 + chaine2;
cout << chaine1 << endl;
chaine1 += chaine3;
cout << chaine1 << endl << endl;;
 
//Concatenation effectuee par la fonction append()
cout << "Concatenation effectuee par la fonction append() :" << endl;
string chaine4("de la foret de Perdagne");
chaine1.append(chaine4);
cout << chaine1 << endl << endl;
 
//Peut également être concatene avec un tableau de style-C
cout << "Peut egalement etre concatene avec un tableau de style-C :" << endl;
string chaine5("Nous chassons les Gobelins ");
const char *tab = { "de la Roche aux Bois" };
chaine5.append(tab);
cout << chaine5 << endl << endl;
 
//Utilisation des fonctions erase() et insert()
cout << "Utilisation des fonctions erase() et insert() :" << endl;
chaine5.erase(27, 20);
cout << chaine5 << endl;
chaine5.insert(27, chaine4);
cout << chaine5 << endl << endl;
 
 
//Utilisation de la fonction replace()
//Un raccourci qui évite erase() et insert()
cout << "La fonction replace() evite l'utilisation des fonctions erase()" << endl;
cout << "et insert() :" << endl;
string chaine6("de la Caverne aux Rats");
chaine5.replace(27, chaine4.size(), chaine6);
cout << chaine5 << endl;
 
_getch();
 
return 0;
 
} 

 

   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. wink

   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()smiley

 

   Exemple :

      Projet 141ContSequentiels_10 

 

//Projet 141ContSequentiels_10
//Opérations de recherche sur les chaînes
//Recherche d'une sous-chaîne et d'un caractère donné
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
 
int main()
{
 
string chaine("Nabuchodonosor roi de Babylone");
 
cout << endl;
cout << "Initialisation d'une chaine." << endl;
cout << "La chaine est : " << chaine << endl << endl;
cout << "Nous recherchons premierement la sous-chaine 'roi'" << endl;
 
//Recherche de la sous-chaîne 'roi'
size_t debut(0);
auto position = chaine.find("roi", debut);
 
if (position != string::npos)
cout << "La sous-chaine 'roi' se trouve en position " << position << endl << endl;
else
cout << "La sous-chaine 'roi' n'est pas dans la chaine !" << endl << endl;
 
string chaine2("Le grand roi Nabuchodonosor, roi de Babylone");
 
cout << "Initialisation d'une seconde chaine." << endl;
cout << "La chaine est : " << chaine2 << endl << endl;
cout << "Nous recherchons maintenant toutes les occurrences" << endl;
cout << "de la sous-chaine 'roi'" << endl;
 
//Recherche du nb d'occurrences de la sous-chaîne 'roi'
 
size_t nb_occurrences(0);
debut = 0;
position = chaine2.find("roi", debut);
 
while (position != string::npos)
{
cout << "La sous-chaine 'roi' se trouve en position " << position << endl;
nb_occurrences++;
 
debut = position + 1;
position = chaine2.find("roi", debut);
}
 
cout << "La sous-chaine 'roi' a ete trouvee " << nb_occurrences << " fois." << endl << endl;
 
//Recherche d'un caractère dans la chaîne
cout << "Nous allons egalement rechercher toutes les occurrences" << endl;
 
cout << "du caractete 'o' dans la chaine :" << endl;
 
const char caract('o');
debut = 0;
nb_occurrences = 0;
position = chaine2.find(caract, debut);
 
while (position != string::npos)
{
cout << "Le caractere 'o' se trouve en position " << position << endl;
nb_occurrences++;
debut = position + 1;
position = chaine2.find(caract, debut);
}
 
cout << "Le caractere 'o' a ete trouve " << nb_occurrences << " fois." << endl;
 
_getch();
return 0;
 
}  

 

   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. wink

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

 

 

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

 

 

  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().

 

Fonctions d'opérations de recherche sur les chaînes
chaine.find(params)  Trouve la première occurrence de params dans chaine.
chaine.rfind(params) Trouve la dernière occurrence de params dans chaine.
chaine.find_first_of (params)  Trouve la première occurrence d'un caractère quelconque de params dans chaine.
chaine.find_last_of (params) Trouve la dernière occurrence d'un caractère quelconque de params dans chaine.
chaine.find_first_not_of (params) Trouve le premier caractère de chaine qui ne se trouve pas dans params.
chaine.find_last_not_of (params) Trouve le dernier caractère de chaine qui ne se trouve pas dans params.

 



   Quelques exemples : 

string nom = "Gondulzak";
auto pos = nom.find("Gondul");
cout << pos << endl;

   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.

string nom_en_minuscules("gondulzak");
pos = nom_en_minuscules.find("Gondul");
cout << pos << endl;

 

   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''.

string name("Gondulzak");
string sous_chaine("G0ndul");
pos = sous_chaine.find_first_not_of(name);
cout << pos << endl;  

   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''. cheeky

 


   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 :

string nombres("123456789");
string formule("H3N1");
string::size_type pos = 0; //la recherche commencera à l'index 0
 
while ((pos = formule.find_first_of(nombres, pos)) != string::npos)
{
cout << "Un chiffre a ete trouve a l'index " << pos << endl;
cout << "Le chiffre est " << formule[pos] << endl;
++pos;
}

 

   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'' :

auto derniere_pos = chaine2.rfind("roi");
cout << "La sous-chaine " << "roi" << " se trouve en position " << derniere_pos << endl;

    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 chaine2wink

 

   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 ! cheeky laugh

 

   Projet 142ContSequentiels_11   

 

//Projet 142ContSequentiels_11
//Opération de comparaison de chaînes
//Utilisation de la fonction STL "compare"
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
 
int main()
{
string ch1 = "Jeremie";
string ch2 = "Assourbanipal";
 
auto result = ch1.compare(ch2);
cout << endl;
cout << "On compare les chaines " << "'" << ch1 << "'" << " et " << "'" << ch2 << "'" << endl;
cout << result << endl;
cout << "Resultat = " << result << " donc " << "'" << ch1 << "'" << " > " << "'" << ch2 << "'" << endl;
 
_getch();
return 0;
} 

 

 

 

   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.

 

 Arguments possibles de la fonction compare()
 chaine1.compare(chaine2) compare chaine1 à chaine2.
chaine1.compare(pos1, n1, chaine2) compare à chaine2, n1 caractères à partir de l'index pos1 de chaine1.
chaine1.compare(pos1, n1, pos2, n2, chaine2) compare n1 caractères à partir de l'index pos1 de chaine1 à n2 caractères à partir de l'index pos2 de chaine2.

  
    

      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) :

string ch1 = "Legends of Meruvia";
string ch2 = "Meruvia, the legend";
auto pos1 = 11;
auto n1 = 7;
auto result = ch1.compare(pos1, n1, ch2);
cout << result << endl; 

 

   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. wink

 

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

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

string ch1 = "Legends of Meruvia";
string ch2 = "Meruvia, the legend";
auto pos1 = 3;
auto pos2 = 16;
auto n1 = 3;
auto n2 = 2;
auto result = ch1.compare(pos1, n1, ch2, pos2, n2);
cout << result << endl;

 

   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. angel

 


   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.

 

Conversions entre chaînes et nombres
to_string(valeur) Fonctions surchargées qui retournent sous forme de chaîne une valeur numérique. Les différentes versions de to_string() supportent la conversion de valeurs entières, ou en virgule flottante.
stoi (chaine)  Retourne la chaîne passée en paramètre en valeur numérique entière.
stol (chaine)  Retourne la chaîne passée en paramètre en une valeur de type long.
stoul (chaine) Retourne la chaîne passée en paramètre en une valeur unsigned long.
stoll (chaine) Retourne la chaîne passée en paramètre en une valeur unsigned long long.
stof (chaine) Retourne la chaîne passée en paramètre en une valeur de type float.
stod (chaine) Retourne la chaîne passée en paramètre en une valeur de type double.
stold (chaine)  Retourne la chaîne passée en paramètre en une valeur de type long double.

 


   Quelques exemples :

string chaine;
int val = 128;
 
chaine = to_string(val);
cout << val << endl;

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

string chaine = "128";
val = stod(chaine);
cout << val << endl;

   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.

 

Opérations et types communs aux conteneurs adaptatifs
size_type Type suffisamment grand pour contenir la plus grande taille de l'objet de ce type.
value_type Type d'un élément.
container_type Type de conteneur sur lequel l'adaptateur est implémenté.
adaptateur ad Crée un nouvel adaptateur dénommé ad.
adaptateur ad1 (ad2) Crée un nouvel adaptateur dénommé ad1 avec une copie du conteneur ad2.
opérateurs relationnels  Tous les adaptateurs supportent les opérateurs relationnels : = =, !=, <, <=, >, >=. Ces opérateurs retournent le résultat de la comparaison avec les conteneurs liés.
ad.empty() Vrai si ad est vide. Faux dans le cas contraire.
ad.size()  Nombre d'éléments dans ad.
swap (ad1, ad2) Echange le contenu de ad1 et ad2. Ceux-ci doivent être de même type, y compris le type des conteneurs sur lesquels ils sont implémentés.
ad.pop() Supprime mais ne retourne pas l'élément supérieur de la pile.
ad.push(elem) Crée un nouvel élément au sommet de la pile, par copie ou déplacement.
ad.emplace(elem) Construit un nouvel élément au sommet de la pile à partir de elem.
ad.top() Retourne mais ne supprime pas l'élément supérieur de la pile.

 

 

 

      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 :

//Pile vide implémentée à partir d'un vector de strings.
stack<string, vector<string>> myStack_of_Strings;
 
//Pile implémentée à partir d'un vector de strings mais contenant initialement une copie d'un autre
//vector.
stack<string, vector<string>> myStack_of_Strings (autreVector);

 


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 

 

//Projet 143ContAdaptatifs_1
//Création, affichage et vidange d'une pile(stack)
#include <iostream>
#include <conio.h>
#include <stack>
 
using namespace std;
 
 
int main()
{
 
//Initialisation d'une pile vide
stack<int> myStackInts;
int nombre(0);
 
//On remplit la pile avec les 15 premiers entiers
cout << endl;
cout << "On remplit la pile avec les 15 premiers entiers." << endl;
cout << "On affiche un element et on le supprime ensuite." << endl;
for (size_t x = 0; x != 15; ++x)
myStackInts.push(x);
cout << endl;
 
//On affiche le nombre du dessus de la pile et on le supprime
while (!myStackInts.empty())
{
nombre = myStackInts.top();
cout << nombre << " ";
myStackInts.pop();
}
 
cout << endl << endl;
 
//Maintenant la pile est vide
if (myStackInts.empty())
cout << "Maintenant la pile est vide !" << endl;
else cout << "La pile n'est pas vide !" << endl;
 
_getch();
return 0;
 
} 

 

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

   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 wink).

   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 ! surprise

   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. cheeky Cette façon de procéder est identique à une file FIFO (First in, First out). wink

   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 queuewink

 

   Exemple :

      Projet 144ContAdaptatifs_2 

 

//Projet 144ContAdaptatifs_2
//Création, affichage et vidange d'une file(queue)
#include <iostream>
#include <conio.h>
#include <queue>
 
using namespace std;
 
 
int main()
{
 
//Initialisation d'une file vide
queue<int> myQueueInts;
int nombre(0);
 
//On remplit la file avec les 15 premiers entiers
cout << endl;
cout << "On remplit la file avec les 15 premiers entiers." << endl;
cout << "On affiche un element et on le supprime ensuite." << endl;
for (size_t x = 0; x != 15; ++x)
myQueueInts.push(x);
//
cout << endl;
 
//On affiche la valeur des élément de début et fin de liste
 
cout << "Les elements de debut et fin de file sont respectivement ";
cout << myQueueInts.front() << " et ";
cout << myQueueInts.back() << endl;
;
//On affiche le nombre du debut de la file et on le supprime
while (!myQueueInts.empty())
{
nombre = myQueueInts.front();
cout << nombre << " ";
myQueueInts.pop();
}
 
cout << endl << endl;
 
//Maintenant la file est vide
if (myQueueInts.empty())
cout << "Maintenant la file est vide !" << endl;
else cout << "La file n'est pas vide !" << endl;
 
_getch();
return 0;
 
} 

 

      Ici nous devons inclure le fichier header <queue> au debut du programme. On remplit la file de la même manière que sur l'exemple d'un adaptateur stack et on affiche les éléments de début et de fin de file à l'aide des méthodes front() et back().

   Nous allons afficher tous les éléments de la file tant que celle-ci n'est pas vide. Pour ce faire, nous donnons à notre variable nombre la valeur de l'élément du début de l'adaptateur soit myQueueInts.front() et nous supprimons l'élément par l'intermédiaire de la méthode pop().

   Ce qui donne comme résultat dans la console :

 

 

   Nous avons créé un adaptateur queue ''vide'' au départ du programme mais celui-ci pouvait être initialisé à l'aide d'un conteneur de type deque ou list. Ceci veut dire que si nous avions par exemple créé un conteneur list au départ, contenant lui-même les éléments 0… 14, nous aurions pu écrire le constructeur de notre adaptateur queue de cette façon :

//Création d'un conteneur list d'entiers ( 0...14)
list<int> myList;
for (int i = 0; i != 15; ++i)
myList.push_back(i);
 
//Initialisation d'une file à partir du conteneur myList
queue<int, list<int>> myQueueInts(myList);

 

 

   1.4 – L'adaptateur ''priority_queue'' 

 

   L'adaptateur priority_queue définit un adaptateur queue dans lequel tous les éléments sont ordonnés.

   Il s'ensuit que priority_queue est défini dans le header <queue> qu'il ne faut pas omettre d'inclure en début de programme. wink

   Dans un adaptateur priority_queue, l'élément possédant la priorité la plus haute (par défaut le plus grand élément), se trouvera au début de la liste des éléments.

   Puisque l'adaptateur priority_queue est un adaptateur queue, seul le premier élément est accessible, ce qui implique que l'élément ayant la plus haute priorité sera traité en premier.

 

Opérations relatives à l'adaptateur priority_queue
pq.push(elem) Ajoute un nouvel élément dans le conteneur, à une place appropriée de la séquence, ce qui habituellement implique une opération de tri.
pq.emplace(elem) Construit un nouvel élément dans le conteneur, à une place appropriée de la séquence, ce qui habituellement implique une opération de tri pour maintenir l'ordre de priorité.
pq.top() Retourne une référence sur le premier élément de la priority_queue.
pq.pop() Supprime le premier élément.
pq.size() Retourne le nombre d'élément dans priority_queue.
pq.empty() Retourne ''vrai'' si la priority_queue est vide.
swap(priority_queue<type> &autre)

Echange les contenus de deux conteneurs. Les éléments de l'un doivent être de même type que les éléments de l'autre.

 


   Création d'une priority_queue
 

   Nous pouvons créer une priority_queue vide, soit :

priority_queue<string> Personnages;     

 

    Nous pouvons également créer une priority_queue à partir d'un tableau de chaînes :

string Personnages[] { "Rabidja", "Aron", "Arwel", "Wiwi" };
priority_queue<string> mes_Personnages{ begin(Personnages), end(Personnages) };    

 

  Ces chaînes de caractères seront alors affichées selon un ordre à partir de leur plus haute priorité.

//On affiche la chaîne du début de la file et on la supprime
string chaine;
while (!mesPersonnages.empty())
{
chaine = myPersonnages.top();
cout << chaine << " ";
myPersonnages.pop();
}

 

   Ce qui naturellement affichera : Wiwi Rabidja Arwel Aron.

   Création à partir d'un vector de strings :

vector<string> Heros { "Rabidja", "Aron", "Arwel", "Wiwi" };
priority_queue<string, vector<string>> mes_Heros{ begin(Heros), end(Heros) };
 
while (!mes_Heros.empty())
{
chaine = mes_Heros.top();
cout << chaine << " ";
mes_Heros.pop();
}

 

   Nous pouvons aussi créer une priority_queue en utilisant l'opération ''greater'' du fichier header <functional>. Les éléments seront alors stockés dans un ordre opposé, l'élément le plus petit étant alors l'élément ayant la plus grande priorité.

string Heros[] { "Rabidja", "Aron", "Arwel", "Wiwi" };
priority_queue<string, vector<string>, greater<string>> mes_Heros{ begin(Heros),
end(Heros) };
 
while (!mes_Heros.empty())
{
chaine = mes_Heros.top();
cout << chaine << " ";
mes_Heros.pop();
}

   affichera cette fois : Aron Arwel Rabidja Wiwi


   Nous allons montrer dans un exemple, un programme qui illustre diverses constructions et manipulations d'un adaptateur priority_queue avec des entiers cette fois.

 

   Exemple :

      Projet 145ContAdaptatifs_3 

 

//Projet 145ContAdaptatifs_3
//Construction d'adaptateurs priority_queue
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <conio.h>
 
using namespace std;
 
 
int main()
{
int mesEntiers[] = { 10, 40, 70, 20, 50, 30, 100, 80, 60, 90 };
int nombre(0);
 
priority_queue<int> premiere_File;
 
if (premiere_File.empty())
cout << "La file 'premiere_File' est vide !" << endl;
else cout << "La file 'premiere_File' n'est pas vide !" << endl;
 
priority_queue<int> seconde_File(mesEntiers, mesEntiers + 5);
 
if (seconde_File.empty())
cout << "La file 'seconde_File' est vide !" << endl;
else cout << "La file 'seconde_File' n'est pas vide !" << endl;
cout << endl;
 
cout << "L'element de plus haute priorite dans 'seconde_File' est ";
cout << seconde_File.top() << endl << endl;
 
cout << "Elements de la file 'seconde_File' :" << endl;
 
//Afichage des éléments de seconde_File par priorité et suppression
while (!seconde_File.empty())
{
nombre = seconde_File.top();
cout << nombre << " ";
seconde_File.pop();
}
 
cout << endl << endl;
//Constructeur utilisant l'operation 'greater' du header <functional>
//Crée une priority_queue à partir d'un vector dont les éléments à partir
//du plus petit vers le plus grand sont entrés dans la file.
priority_queue<int, std::vector<int>, std::greater<int>>
troisieme_File(mesEntiers, mesEntiers + 5);
 
if (troisieme_File.empty())
cout << "La file 'troisieme_File' est vide !" << endl;
else cout << "La file 'troisieme_File' n'est pas vide !" << endl;
cout << endl;
 
cout << "L'element de plus haute priorite dans 'troisieme_File_File' est ";
cout << troisieme_File.top() << endl << endl;
 
cout << "Elements de la file 'troisieme_File' :" << endl;
 
//Maintenant on ajoute un nouveau nombre dans la file
troisieme_File.push(35);
 
//Afichage des éléments de troisieme_File par priorité et suppression
while (!troisieme_File.empty())
{
nombre = troisieme_File.top();
cout << nombre << " ";
troisieme_File.pop();
}
 
_getch();
return 0;
} 

 

     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. wink

   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 ?''. indecision

   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. cheeky

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

   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 :

1. Roswyn priorité haute supérieure
2. Wiwi priorité haute
3. Aron priorité moyenne supérieure
4. Rabidja priorité moyenne
5. Arwell priorité faible

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

   Toutes les explications nécessaires suivront par la suite. wink

 

   Projet 146ContAdaptatifs_4 

 

//Projet 146ContAdaptatifs_4
//Organiser une priorité dans une priority_queue
#include <iostream>
#include <queue>
#include <string>
#include <conio.h>
 
using namespace std;
 
// Type des données stockées dans la file
struct Personne
{
//Constructeur
Personne(int priority, const string nom) : _priority(priority), _nom(nom) {}
 
string _nom; // Nom
int _priority; // Priorité
};
 
 
// Foncteur de comparaison selon les priorités
class Comparaison
{
public:
 
bool operator() (const Personne &pers1, const Personne &pers2)
{
return pers1._priority < pers2._priority;
}
};
 
 
int main(void)
{
// Construction des objets selon une priorité désirée
Personne p1(1, "Arwell - Priorite faible");
Personne p2(2, "Rabidja - Priorite moyenne");
Personne p3(3, "Aron - Priorite moyenne sup");
Personne p4(4, "Wiwi - Priorite haute");
Personne p5(5, "Roswyn - Priorite haute sup");
 
// On construit une file de priorité :
priority_queue<Personne, vector<Personne>, Comparaison> pq;
 
// On ajoute les éléments dans n'importe quel ordre:
pq.push(p3);
pq.push(p2);
pq.push(p5);
pq.push(p1);
pq.push(p4);
 
// On récupère les éléments par ordre de priorité voulue au départ
cout << endl;
while (!pq.empty())
{
cout << pq.top()._nom << endl;
pq.pop();
}
 
_getch();
return 0;
} 

 

      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. wink

   Ce qui affiche dans la console :

 

  

   Allez, pourquoi pas un second challenge ? angel

 

 

   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... frown

 


   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 : 

 

//Projet Chap23Exercice_1
//Supprimer des éléments dans un conteneur forward_list
#include <iostream>
 
#include <conio.h>
#include <forward_list>
 
using namespace std;
using uint = unsigned int;
 
int main()
 
{
//Initialisation d'une forward_list d'unsigned int
forward_list<uint> fList = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
 
cout << endl;
cout << "Creation d'une forward_list de 15 valeurs de type unsigned" << endl;
cout << "Lecture de la liste :" << endl << endl;
 
auto precedent = fList.before_begin();
auto courant = fList.begin();
 
//On affiche la liste
while (courant != fList.end())
{
cout << *courant << " ";
precedent = courant;
++courant;
}
 
//Maintenant on supprime tous les éléments impairs
//et on affiche la liste modifiée
precedent = fList.before_begin();
courant = fList.begin();
 
cout << endl << endl;
cout << "On supprime tous les elements impairs" << endl;
while (courant != fList.end())
{
if (*courant % 2)
courant = fList.erase_after(precedent);
 
else
{
precedent = courant;
++courant;
}
}
 
 
cout << "et on affiche la liste modifiee" << endl << endl;
precedent = fList.before_begin();
courant = fList.begin();
 
while (courant != fList.end())
{
cout << *courant << " ";
precedent = courant;
++courant;
}
 
cout << endl;
 
_getch();
return 0;
} 

 

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

   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. wink

   Ce qui affiche dans la console :

 

  

 

 

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

   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.  angel
 
 
 

Connectez-vous ou inscrivez-vous pour pouvoir poster.