Page suivante Page précédente Table des matières 6. Introduction à STL, la Bibliothèque de Modèles Standards Par Scott Field. 6.1 Introduction Cet article traite d'une nouvelle extension du langage C++, la Bibliothèque de Modèles Standard, également connue sous le nom STL (Standard Template Library). Initialement, lorsque j'ai proposé l'idée de rédiger un article sur STL, je dois dire que j'avais sous-estimé l'étendue et l'importance du sujet. Il y a un tas de choses à dire et il existe de nombreux livres qui décrivent STL en détail. J'ai donc reconsidéré mon idée initiale pour la recentrer. Pourquoi écrire un article et en quoi pouvais-je apporter une contribution ? Qu'est-ce qui pourrait être utile ? Un autre article sur STL était-il nécessaire ? En feuilletant les pages du Musser et Saini, j'ai pu voir les temps de programmation se dissoudre devant moi. J'ai pu voir les longues soirées de travail disparaître et les projets logiciels terminés à temps réapparaître. J'ai redécouvert un code dont la maintenance est possible. Depuis, un an s'est écoulé et le logiciel que j'ai écrit en utilisant STL s'est révélé remarquablement facile à maintenir. Et, ce qui est surprenant, les autres peuvent également le maintenir, sans mon aide ! Je me souviens cependant qu'au début, il m'a été difficile de venir à bout de ce jargon technique. Après avoir acheté le Musser & Saini, tout s'est mis en place, mais après une rude bataille et avec l'envie de disposer de bons exemples. De plus, la troisième édition de Stroustrup, qui traite de STL comme faisant partie de C++, n'était pas disponible quand j'ai commencé. Aussi, j'ai pensé qu'il pourrait être utile d'écrire un article sur l'utilisation réelle de STL pour de nouveaux programmeurs STL. J'ai toujours appris plus rapidement lorsque je pouvais disposer de bons exemples, particulièrement pour de nouveaux sujets tels que celui-ci. D'un autre côté, on suppose que STL est facile à utiliser. Donc, on devrait théoriquement être capable d'utiliser STL directement sans problème. Qu'est-ce que STL ? STL est l'acronyme de "Standard Template Library", ou Bibliothèque de Modèles Standards. C'est probablement l'un des termes les plus ennuyeux pour l'un des outils les plus excitants de l'histoire. Fondamentalement, STL est constituée d'un ensemble de conteneurs ( listes, vecteurs, ensembles, correspondances et autres ), d'un ensemble d'algorithmes et d'autres composants. La création de cet "ensemble de conteneurs et d'algorithmes" a pris plusieurs années à quelques uns des gens les plus brillants de ce monde. L'objectif de STL est de standardiser les composants utilisés habituellement afin de ne pas avoir à les réinventer. Vous pouvez utiliser les composants de STL directement. STL fait maintenant partie de C++, il n'y a donc plus de pièces et de morceaux supplémentaires à trouver et à installer. Il font partie de votre compilateur. La liste étant l'un des conteneurs les plus simples de STL, je pense qu'elle constitue un candidat idéal pour commencer à montrer l'utilisation pratique de STL. Si vous en saisissez les concepts, vous n'aurez aucun problème avec les autres. De plus, comme vous pourrez le voir, les possibilités sont impressionnantes pour un simple conteneur de liste. Dans cet article, nous verrons comment définir et initialiser une liste, en compter les éléments, retrouver les éléments d'une liste et en enlever ainsi que d'autres opérations très utiles. Ce faisant, nous étudierons deux sortes différentes d'algorithmes, les algorithmes génériques STL qui fonctionnent avec plus d'un conteneur et les fonctions membres de liste qui ne travaillent exclusivement qu'avec le conteneur de liste. Juste au cas où quelqu'un se poserait la question, voici une brève description des trois principales sortes de composants de STL. Les conteneurs contiennent des objets, incorporent des objets et des classes d'objets. Ils en assurent l'intégrité et définissent une interface standard à travers laquelle on peut les manipuler. Les oeufs, dans un conteneur à oeufs, ne risquent pas de dégringoler de l'étagère. Ils sont en sûreté. Il en est de même pour les objets dans les conteneurs STL. Ils sont en sûreté. Je sais que c'est banal, mais c'est vrai. Les algorithmes de STL sont des algorithmes standards que l'on peut utiliser pour les objets qui sont dans le conteneur. Ces algorithmes ont des caractéristiques d'exécution parfaitement connues. Ils peuvent trier les objets, les enlever, les compter, les comparer, en retrouver un en particulier, insérer les objets dans un autre conteneur et effectuer beaucoup d'autres opérations utiles. Les itérateurs sont comme des pointeurs sur les objets dans les conteneurs. Les algorithmes de STL utilisent les itérateurs pour agir sur les conteneurs. Les itérateurs fixent les bornent pour les algorithmes, en se référant à l'étendue du conteneur et par d'autres moyens. Par exemple certains itérateurs laissent seulement les algorithmes lire les éléments, certains leurs permettent d'écrire, d'autres les deux. Les itérateurs déterminent également la direction du traitement dans un conteneur. Vous pouvez positionner un itérateur en première position d'un conteneur en appelant la fonction membre begin(). Pour aller à la dernière valeur d'un conteneur vous pouvez appeler la fonction end() ( où le traitement s'arrête ). STL, c'est cela, des conteneurs, des algorithmes et des itérateurs pour permettre aux algorithmes de travailler sur les éléments des conteneurs. Les algorithmes manipulent les objets de manière standard, mesurable, et sont au courant de la taille précise des conteneurs via les itérateurs. Quand on a fait cela, il n'y a jamais de débordement. Il existe d'autres composants qui augmentent les fonctionnalités de ces composants types de base, comme les objets fonction. Nous en verrons également quelques exemples. Pour l'instant, jetons un oeil à la liste STL. 6.2 Définition d'une liste On peut définir une liste STL de cette façon : #include <string> #include <list> int main (void) { list<string> Milkshakes; } C'est tout. Vous avez défini une liste. Cela pourrait-il être plus simple ? En écrivant list<string> Milkshakes, vous avez créé un exemplaire d'un modèle de classe list<string>, puis créé un objet de ce type. Mais ne nous en faisons pas pour ça. Pour l'instant, ce que l'on a réellement besoin de savoir, c'est que vous avez défini une liste de chaînes de caractères. Il faut le fichier d'en-tête list pour définir la classe STL list. J'ai compilé ces programmes de test en utilisant GCC 2.7.2 sur ma machine Linux ( NdT : j'ai fait de même en utilisant egcs-1.0.3 ). Par exemple : g++ test1.cpp -otest1 Noter que le fichier d'en-tête iostream.h est inclus dans l'un des fichiers en-tête de STL. C'est la raison pour laquelle on ne le trouve pas dans certains exemples. Maintenant que nous avons une liste, nous pouvons commencer à l'utiliser pour y ranger des choses. Nous allons ajouter quelques chaînes de caractères à cette liste. Le type de valeur des éléments est le type de l'objet que contient la liste. Dans ce cas, le type de valeur de la liste est la chaîne de caractères ( string ), puisque la liste contient des chaînes de caractères. 6.3 Insertion d'éléments dans une liste en utilisant les fonctions membres de liste push_back et push_front #include <string> #include <list> # int main (void) { list<string> Milkshakes; Milkshakes.push_back("Chocolate"); Milkshakes.push_back("Strawberry"); Milkshakes.push_front("Lime"); Milkshakes.push_front("Vanilla"); } Nous avons obtenu une liste contenant quatre chaînes de caractères. La fonction membre de liste push_back() place un objet en queue de liste. La fonction membre push_front() le met en tête de liste. Je met fréquemment les messages d'erreur en queue de liste (push_back()), et ensuite, insère un titre en tête de liste (push_front()) de façon à ce qu'il soit imprimé avant les messages d'erreur. 6.4 La fonction membre de liste empty() Il est important de savoir si une liste est vide. La fonction membre de liste retourne la valeur vrai si la liste est vide. Le fait d'être vide constitue un concept d'une simplicité trompeuse. Je l'utilise souvent de la manière suivante. Tout au long d'un programme j'utilise push_back() pour stocker les messages d'erreur dans une liste. Puis, en utilisant empty(), je peux dire s'il y a eu des erreurs d'exécution. Si je défini une liste pour les messages d'information, une liste pour les messages d'avertissement et une pour les erreurs sérieuses, je peux facilement dire quels types d'erreurs se sont produits en utilisant uniquement empty(). Je peux renseigner ces listes tout au long du programme, puis les habiller d'un titre ou éventuellement les trier par catégories avant de les imprimer. Voici ce que je veux dire. /* * Utilisation d'une pour liste pour enregistrer et éditer les messages et * l'état d'un programme */ #include <iostream.h> #include <string> #include <list> # int main (void) { #define OK 0 #define INFO 1 #define WARNING 2 # int return_code; # list<string> InfoMessages; list<string> WarningMessages; # // au cours du programme ces messages sont enregistrés en différents points InfoMessages.push_back("Info: Programme lancé"); // do work... WarningMessages.push_back("Attention: Aucun enregistrement client n'a été trouvé"); // effectue les traitements... # return_code = OK; # if (!InfoMessages.empty()) { // il y a eu des messages d'info InfoMessages.push_front("Messages d'information :"); // ... imprimer la liste des messages d'info, nous verrons comment plus tard return_code = INFO; } # if (!WarningMessages.empty()) { // il y a eu des messages d'avertissement WarningMessages.push_front("Messages d'avertissement :"); // ... imprimer la liste des messages d'avertissement, nous verrons comment plus tard return_code = WARNING; } # // S'il n'y a pas eu de messages, le dire. if (InfoMessages.empty() && WarningMessages.empty()) { cout << "Il n'y a pas eu de messages " << endl; } # return return_code; } 6.5 Traitement des éléments d'une liste avec une boucle for Nous voudrions pouvoir faire des itérations à travers n'importe quelle liste pour, par exemple, imprimer tous les objets de la liste afin de voir les effets de différentes opérations sur cette liste. Pour réaliser ces itérations à travers une liste, élément par élément, nous pouvons procéder comme suit : /* * Comment imprimer le contenu d'une simple liste STL. Whaouh ! */ #include <iostream.h> #include <string> #include <list> # int main (void) { list<string> Milkshakes; list<string>::iterator MilkshakeIterator; # Milkshakes.push_back("Chocolate"); Milkshakes.push_back("Strawberry"); Milkshakes.push_front("Lime"); Milkshakes.push_front("Vanilla"); # // imprimer les milkshakes Milkshakes.push_front("The Milkshake Menu"); Milkshakes.push_back("*** C'est fini ! ***"); for (MilkshakeIterator=Milkshakes.begin(); MilkshakeIterator!=Milkshakes.end(); ++MilkshakeIterator) { // déréférencer l'itérateur pour obtenir l'élément cout << *MilkshakeIterator << endl; } } Dans ce programme, nous définissons un itérateur MilkshakeIterator. Nous initialisons MilkshakeIterator pour le faire pointer sur le premier élément de la liste. Pour ce faire, on exécute un appel à Milkshakes.begin() qui retourne un itérateur pointant sur le début de la liste. Ensuite, nous comparons MilkshakeIterator à la valeur de fin de liste Milkshakes.end(), et stoppons la boucle lorsque nous avons égalité. La fonction end() d'un conteneur retourne un itérateur pointant sur la position juste après la fin du conteneur. Lorsque l'on arrive là, on arrête le traitement. On ne peut pas accéder à la donnée pointée par l'itérateur retourné par la fonction end() du conteneur. Nous savons seulement que nous avons dépassé la fin du conteneur et que nous devons arrêter le traitement de ses éléments. Ceci est valable pour tous les conteneurs STL. Dans l'exemple ci-dessus, à chaque passe dans la boucle for nous accédons à la chaîne de caractères pointée par l'itérateur, et nous imprimons cette chaîne. En programmation STL, nous utilisons un ou plusieurs itérateurs dans chaque algorithme. Nous les utilisons pour accéder aux objets qui sont dans un conteneur. Pour accéder à un objet donné, nous déplaçons l'itérateur sur l'objet en question, puis nous accédons à l'objet par l'intermédiaire de l'itérateur. (NdT : en jargon, on dirait que nous déréférençons l'itérateur). Le conteneur de liste, au cas où vous poseriez la question, ne permet pas d'accéder à un autre objet dans le conteneur en ajoutant un nombre à l'itérateur de liste courant. C'est-à-dire que nous ne pouvons pas dire que Milkshakes.begin()+2 pointe sur le troisième objet de la liste, car la liste STL est implémentée comme une liste doublement chaînée qui ne supporte pas l'accès direct. Les conteneurs vector et deque, qui sont d'autres conteneurs STL, permettent l'accès direct. Le programme ci-dessus imprime le contenu d'une liste. N'importe qui, lisant ce programme, voit immédiatement comment il marche. Il utilise un itérateur standard et une liste standard. Il n'y a pas beaucoup de choses qui dépendent du programmeur à l'intérieur, ou de l'implémentation maison d'une gestion de liste. C'est uniquement du C++ standard. C'est un important pas en avant. Même cette utilisation simple de STL rend notre logiciel plus standard. 6.6 Traitement des éléments d'une liste avec l'algorithme générique STL for_each Même avec une liste et un itérateur STL, nous devons initialiser, tester et incrémenter l'itérateur pour nous déplacer dans un conteneur. L'algorithme générique STL for_each peut nous soulager de ce travail. /* * Comment imprimer une simple liste STL MkII */ #include <iostream.h> #include <string> #include <list> #include <algorithm> # PrintIt (string& StringToPrint) { cout << StringToPrint << endl; } # int main (void) { list<string> FruitAndVegetables; FruitAndVegetables.push_back("carrot"); FruitAndVegetables.push_back("pumpkin"); FruitAndVegetables.push_back("potato"); FruitAndVegetables.push_front("apple"); FruitAndVegetables.push_front("pineapple"); # for_each (FruitAndVegetables.begin(), FruitAndVegetables.end(), PrintIt); } Dans ce programme, nous utilisons l'algorithme générique STL for_each() pour répéter, sur l'étendue de l'itérateur, l'invocation de la fonction PrintIt() pour chaque objet. Nous n'avons pas besoin d'initialiser, de tester ou d'incrémenter un quelconque itérateur. for_each(), de manière sympathique, rend notre code modulaire. L'opération que nous effectuons sur un objet est agréablement réalisée par une fonction, on est débarrassé de la gestion de la boucle et notre code est plus clair. L'algorithme for_each introduit le concept de domaine de l'itérateur, spécifié par un itérateur de début et un itérateur de fin. L'itérateur de début indique où doit commencer le traitement et l'itérateur de fin spécifie où doit le traitement doit s'arrêter, cet itérateur de fin ne faisant pas partie du domaine. 6.7 Comptage des éléments d'une liste avec l'algorithme générique STL count() Les algorithmes génériques STL count() et count_if() comptent les occurrences des objets dans un conteneur. De même que pour for_each(), les algorithmes count() et count_if() ont un domaine pour l'itérateur. Comptons le nombre de résultats les meilleurs possibles dans une liste de résultats d'étudiants à un examen, c'est une liste d'entiers. /* * Comment compter les objets dans une liste STL */ #include <list> #include <algorithm> # int main (void) { list<int> Scores; # Scores.push_back(100); Scores.push_back(80); Scores.push_back(45); Scores.push_back(75); Scores.push_back(99); Scores.push_back(100); # int NumberOf100Scores(0); count (Scores.begin(), Scores.end(), 100, NumberOf100Scores); # cout << "Il y a eu " << NumberOf100Scores << " résultats à 100" << endl; } L'algorithme count() compte le nombre d'objets égaux à une certaine valeur. Dans l'exemple ci-dessus, il compare chaque objet ( nombre entier ) à 100 dans une liste. Il incrémente la variable NumberOf100Scores chaque fois qu'un objet du conteneur est égal à 100. La sortie du programme donne : Il y a eu 2 résultats à 100 6.8 Comptage des éléments d'une liste avec l'algorithme générique STL count_if() count_if() est une version beaucoup plus intéressante de count(). Il introduit un nouveau composant STL, l'objet fonction. count_if() prend un objet fonction comme paramètre. Un objet fonction est une classe ayant au moins l'opérateur () défini. Quelques algorithmes STL acceptent des objets fonctions comme paramètres et invoquent l'opérateur () de l'objet fonction pour chaque objet du conteneur traité. Les objets fonctions destinés à être utilisés par les algorithmes STL ont leurs opérateurs d'appel de fonctions qui retournent les valeurs vrai ou faux. Pour cette raison, on les appelle prédicats objets fonctions. Un exemple va éclaircir ceci. count_if() utilise la valeur passée dans l'objet fonction pour réaliser une évaluation plus complexe que celle de count(), savoir si un objet doit être compté. Dans cet exemple, nous allons compter des brosses à dents vendues. Nous ferons référence aux enregistrements des ventes qui possèdent un code produit à quatre caractères et une description du produit. /* * Utilisation d'un objet fonction pour aider à compter les choses */ #include <string> #include <list> #include <algorithm> # const string ToothbrushCode("0003"); # class IsAToothbrush { public: bool operator() ( string& SalesRecord ) { return SalesRecord.substr(0,4)==ToothbrushCode; } }; # int main (void) { list<string> SalesRecords; # SalesRecords.push_back("0001 Savon"); SalesRecords.push_back("0002 Shampooing"); SalesRecords.push_back("0003 Brosse à dents"); SalesRecords.push_back("0004 Pâte dentifrice"); SalesRecords.push_back("0003 Brosse à dents"); # int NumberOfToothbrushes(0); count_if (SalesRecords.begin(), SalesRecords.end(), IsAToothbrush(), NumberOfToothbrushes); # cout << "Il y a eu " << NumberOfToothbrushes << " brosses à dents vendues" << endl; } La sortie du programme donne : Il y a eu 2 brosses à dents vendues Le programme fonctionne comme ceci : une classe d'objets fonctions est définie, IsAToothbrush. Les objets de cette classe peuvent déterminer si un enregistrement de vente concerne la brosse à dents ou pas. Leur opérateur () d'appel de fonction renverra la valeur vrai si l'enregistrement concerne une vente de brosse à dents ou faux dans le cas contraire. L'algorithme count_if() traitera les objets du conteneur dans le domaine spécifié par le premier et le second paramètres de l'itérateur. Il incrémentera le compteur NumberOfToothbrushes pour chaque objet du conteneur pour lequel IsAToothbrush()() renvoie la valeur vrai. Au résultat, la variable NumberOfToothbrushes contiendra le nombre de ventes enregistrées pour lesquelles le code produit est "0003", c'est-à-dire, qui concernent les brosses à dents. Notez que le troisième paramètre de count_if(), IsAToothbrush(), est un objet temporaire construit à partir de son constructeur par défaut. Les parenthèses () ne signifient pas que c'est un appel de fonction. On passe un objet temporaire de la classe IsAToothbrush à count_if(). count_if() invoquera de manière interne IsAToothbrush()() pour chaque objet du conteneur. 6.9 Un objet fonction plus complexe avec l'algorithme générique count_if() Nous pouvons développer plus avant la notion d'objet fonction. Supposons que nous ayons à passer plus d'informations à un objet fonction. Nous ne pouvons pas le faire en utilisant l'opérateur d'appel de fonction, puisqu'il ne doit être défini que pour prendre un unique objet du type de la liste. Cependant en spécifiant un constructeur qui ne soit pas celui par défaut pour IsAToothbrush nous pouvons l'initialiser avec n'importe quelle information dont nous avons besoin. Nous pourrions avoir besoin d'un code variable pour une brosse à dents par exemple. Nous pouvons ajouter cette information supplémentaire dans l'objet fonction de la façon suivante : /* * Utilisation d'un objet fonction plus complexe */ #include <iostream.h> #include <string> #include <list> #include <algorithm> # class IsAToothbrush { public: IsAToothbrush(string& InToothbrushCode) : ToothbrushCode(InToothbrushCode) {} bool operator() (string& SalesRecord) { return SalesRecord.substr(0,4)==ToothbrushCode; } private: string ToothbrushCode; }; # int main (void) { list<string> SalesRecords; # SalesRecords.push_back("0001 Savon"); SalesRecords.push_back("0002 Shampooing"); SalesRecords.push_back("0003 Brosse à dents"); SalesRecords.push_back("0004 Pâte dentifrice"); SalesRecords.push_back("0003 Brosse à dents"); # string VariableToothbrushCode("0003"); # int NumberOfToothbrushes(0); count_if (SalesRecords.begin(), SalesRecords.end(), IsAToothbrush(VariableToothbrushCode), NumberOfToothbrushes); cout << "Il y a eu " << NumberOfToothbrushes << " brosses à dents ayant le code " << VariableToothbrushCode << " vendues" << endl; } la sortie de ce programme est : Il y a eu 2 brosses à dents portant le code 0003 vendues Cet exemple montre comment passer des informations aux objets fonctions. Vous pouvez définir le constructeur qu'il vous plaira et vous pouvez effectuer le traitement que vous voudrez dans un objet fonction, euh, en tout cas, que le compilateur tolère. Vous pouvez constater que les objets fonctions étendent réellement les possibilités de l'algorithme de comptage de base. Jusqu'à présent, nous avons vu : la définition d'un liste; l'ajout d'éléments à une liste; comment savoir si une liste est vide; comment parcourir une liste en utilisant une boucle for; comment parcourir une liste en utilisant l'algorithme générique STL for_each; les fonctions membres de liste begin() et end() et leur signification; le concept de domaines pour les itérateurs et le fait que la dernière position d'un domaine n'est pas traitée; comment compter les objets d'une liste en utilisant les algorithmes génériques STL count() et count_if(); comment définir des objets fonctions. Ces exemples ont été choisis pour montrer les opérations sur les listes dont on a couramment besoin. Si vous comprenez ces principes de base vous n'aurez aucun problème pour utiliser les efficacement. Pensez que cela nécessite un peu de pratique. Nous allons maintenant élargir nos connaissances avec quelques opérations plus compliquées, 6.10 Trouver des objets dans une liste en utilisant l'algorithme générique STL find() Comment retrouver quelque chose dans une liste ? Les algorithmes génériques STL find() et find_if() le font. Comme pour for_each(), count(), et count_if(), ces algorithmes utilisent un itérateur sur un domaine, spécifiant quelle partie de la liste ou n'importe quel autre conteneur à cet effet, pour effectuer le traitement. Comme d'habitude, le premier itérateur spécifie où commencer le traitement, le second itérateur spécifie où arrêter le traitement. La position spécifiée par le second itérateur ne fait pas partie du traitement. Voici comment travaille find() : /* * Comment trouver des choses dans une liste STL */ #include <string> #include <list> #include <algorithm> # int main (void) { list<string> Fruit; list<string>::iterator FruitIterator; # Fruit.push_back("Apple"); Fruit.push_back("Pineapple"); Fruit.push_back("Star Apple"); # FruitIterator = find (Fruit.begin(), Fruit.end(), "Pineapple"); # if (FruitIterator == Fruit.end()) { cout << "Fruit non trouvé dans la liste" << endl; } else { cout << *FruitIterator << endl; } } La sortie du programme sera : Pineapple Si find ne trouve pas l'objet spécifié, il retourne l'itérateur de dépassement de fin Fruit.end(). Dans le cas contraire, il retourne un itérateur pointant sur l'objet trouvé. 6.11 Trouver des objets dans une liste en utilisant l'algorithme générique STL find_if() Il existe une autre version plus puissante de find(). Cet exemple illustre find_if(), qui accepte un objet fonction comme paramètre et l'utilise pour réaliser une évaluation plus complexe pour "trouver" un objet. Supposons que nous ayons des enregistrements contenant des évènements et des dates rangés par ordre chronologique dans une liste. Nous souhaitons trouver le premier événement ayant eu lieu en 1997. /* * Comment trouver des choses dans une liste STL MkII */ #include <string> #include <list> #include <algorithm> # class EventIsIn1997 { public: bool operator () (string& EventRecord) { // Le champ année est en position 12 pour 4 caractères dans EventRecord return EventRecord.substr(12,4)=="1997"; } }; # int main (void) { list<string> Events; # // string positions 0123456789012345678901234567890123456789012345 Events.push_back("07 Janvier 1995 Plan d'ensemble de la maison"); Events.push_back("07 Février 1996 Plan détaillé de la maison"); Events.push_back("10 Janvier 1997 Ordre de début de travaux du client"); Events.push_back("15 Janvier 1997 L'entreprise commence le chantier par la chambre"); Events.push_back("30 Avril 1997 L'entreprise a terminé les travaux"); # list<string>::iterator EventIterator = find_if (Events.begin(), Events.end(), EventIsIn1997()); # // find_if se termine pour la première fois EventIsIn1997()() renvoie vrai // pour tous les objets. Il retourne un itérateur sur cet objet que nous // pouvons déréférencer pour obtenir l'objet, ou si EventIsIn1997()() ne // retourne jamais vrai, find_if retourne end() if (EventIterator==Events.end()) { cout << "Événement non trouvé dans la liste" << endl; } else { cout << *EventIterator << endl; } } En sortie du programme, on obtiendra : 10 Janvier 1997 Ordre de début des travaux du client 6.12 Recherche de suites dans une liste en utilisant l'algorithme générique STL search Certains caractères sont un peu plus faciles à prendre en compte dans un conteneur STL. Jetons un oeil à une suite de caractères avec laquelle il peut être difficile de travailler. Nous définirons une liste STL pour stocker ces caractères. list<char> Characters; Nous disposons maintenant d'une suite de caractères solide comme le roc qui sait gérer sa mémoire propre sans aucune aide. Elle sait précisément où elle commence et où elle fini. C'est une chose utile. Je ne sais pas si j'ai dit cela au sujet d'un tableau de caractères se terminant par le caractère nul. Ajoutons quelques uns de nos caractères favoris à la liste. Characters.push_back('\0'); Characters.push_back('\0'); Characters.push_back('1'); Characters.push_back('2'); Combien avons nous de caractères nuls ? int NumberOfNullCharacters(0); count(Characters.begin(), Characters.end(), '\0', NumberOfNullCharacters); cout << "We have " << NumberOfNullCharacters << endl; Cherchons le caractère 'l' list<char>::iterator Iter; Iter = find(Characters.begin(), Characters.end(), '1'); cout << "We found " << *Iter << endl; Cet exemple est censé montrer que les conteneurs STL vous permettent de prendre en compte les caractères nuls d'une manière plus standard. Maintenant, cherchons un conteneur pour deux nuls avec l'algorithme de recherche (search()) STL. L'algorithme générique search() recherche dans un conteneur, comme vous l'auriez parié, mais pour une suite d'éléments, à la différence de find() et de find_if() qui ne recherchent qu'un élément simple. /* * comment utiliser l'algorithme search dans une liste STL */ #include <string> #include <list> #include <algorithm> # int main ( void ) { # list<char> TargetCharacters; list<char> ListOfCharacters; # TargetCharacters.push_back('\0'); TargetCharacters.push_back('\0'); # ListOfCharacters.push_back('1'); ListOfCharacters.push_back('2'); ListOfCharacters.push_back('\0'); ListOfCharacters.push_back('\0'); # list<char>::iterator PositionOfNulls = search(ListOfCharacters.begin(), ListOfCharacters.end(), TargetCharacters.begin(), TargetCharacters.end()); # if (PositionOfNulls!=ListOfCharacters.end()) cout << "Nous avons trouvé les nuls" << endl; } La sortie du programme sera : Nous avons trouvé les nuls L'algorithme de recherche trouve la première occurrence d'une suite dans une autre suite. Dans ce cas nous cherchons la première occurrence de TargetCharacters qui est une liste contenant deux caractères nuls, dans ListOfCharacters. Les paramètres de recherche sont deux itérateurs spécifiant un domaine de recherche, et deux itérateurs supplémentaires spécifiant le domaine recherché. Donc, nous cherchons l'ensemble de la liste TargetCharacters dans l'ensemble du domaine de ListOfCharacters. Si TargetCharacters est trouvé, search retournera un itérateur pour le premier caractère de ListOfCharacters où l'on a égalité. Si l'on n'a pas égalité, search retournera la valeur de dépassement de fin ListOfCharacters.end(). 6.13 Tri d'une liste en utilisant la fonction membre de liste sort() Pour trier une liste, nous utilisons la fonction membre de liste sort() et non pas l'algorithme générique sort(). Tous les algorithmes que nous avons utilisé jusqu'à maintenant étaient des algorithmes génériques. Cependant, dans STL, un conteneur fourni quelquefois sa propre implémentation d'un algorithme particulier, soit par nécessité, soit pour améliorer les performances. Dans ce cas le conteneur de liste possède son propre tri car l'algorithme générique de tri ne trie que les conteneurs qui offrent un accès aléatoire aux éléments qu'ils contiennent. Le conteneur de liste ne permet pas l'accès aléatoire aux éléments de la liste car il est implémenté comme une liste chaînée. Une fonction membre spéciale de tri, sort(), est donc nécessaire pour pouvoir trier une liste chaînée. Vous trouverez cela dans STL. Pour des raisons variées les conteneurs fournissent des fonctions supplémentaires, lorsque c'est nécessaire pour des raisons d'efficacité ou parce que des gains de performances peuvent être obtenus en tirant avantage des particularités de la structure du conteneur. /* * comment trier une liste STL */ #include <string> #include <list> #include <algorithm> # PrintIt (string& StringToPrint) { cout << StringToPrint << endl;} # int main (void) { list<string> Staff; list<string>::iterator PeopleIterator; # Staff.push_back("John"); Staff.push_back("Bill"); Staff.push_back("Tony"); Staff.push_back("Fidel"); Staff.push_back("Nelson"); # cout << "Liste non triée " << endl; for_each(Staff.begin(), Staff.end(), PrintIt ); # Staff.sort(); # cout << "Liste triée " << endl; for_each(Staff.begin(), Staff.end(), PrintIt); } La sortie est : Liste non triée John Bill Tony Fidel Nelson Liste triée Bill Fidel John Nelson Tony 6.14 Insertion d'éléments dans une liste avec la fonction membre de liste insert() Les fonctions membre de liste push_front() et push_back() ajoutent des éléments en tête ou en fin de liste respectivement. Vous pouvez également insérer un objet en n'importe quel point de la liste en utilisant insert(). insert() peut ajouter un objet, plusieurs copies d'un objet ou un ensemble d'objets. Voici quelques exemples d'insertion d'objets dans une liste. /* * Utilisation de insert pour insérer des éléments dans une liste. */ #include <list> # int main (void) { list<int> list1; # /* || Mettre les entiers 0 à 9 dans la liste */ for (int i = 0; i < 10; ++i) list1.push_back(i); # /* || Insérer -1 en utilisant la fonction membre || Notre liste contiendra maintenant -1,0,1,2,3,4,5,6,7,8,9 */ list1.insert(list1.begin(), -1); # /* || Insérer un élément en fin de liste en utilisant insert || Notre liste contiendra maintenant -1,0,1,2,3,4,5,6,7,8,9,10 */ list1.insert(list1.end(), 10); # /* || Insertion d'une suite de valeurs provenant d'un autre conteneur || Notre liste contiendra -1,0,1,2,3,4,5,6,7,8,9,10,11,12 */ int IntArray[2] = {11,12}; list1.insert(list1.end(), &IntArray[0], &IntArray[1]); # /* || En guise d'exercice, ajoutez ici le code permettant d'imprimer la liste ! || Indice : utilisez PrintIt en le faisant accepter un entier */ } Notez que la fonction insert() ajoute un ou plusieurs éléments à la position de l'itérateur que vous avez spécifié. Vos éléments apparaîtront dans la liste avant l'élément dont la position est spécifié par l'itérateur. 6.15 Constructeurs de listes Nous avons défini une liste de cette façon : list<int> Fred; Vous pouvez également définir une liste et initialiser ses éléments comme ceci : // définir une liste de 10 éléments et les initialiser tous à 0 list<int> Fred(10, 0); // la liste contient maintenant 0,0,0,0,0,0,0,0,0,0 Ou, vous pouvez définir une liste de 10 éléments et l'initialiser avec les données d'un autre conteneur STL, qui n'a pas forcément besoin d'être une liste, mais simplement un conteneur ayant les mêmes types de valeurs. vector<int> Harry; Harry.push_back(1); Harry.push_back(2); # // définir une liste et l'initialiser avec les éléments de la liste Harry list<int> Bill(Harry.begin(), Harry.end()); // Bill contient maintenant 1,2 6.16 Effacer des éléments d'une liste en utilisant les fonctions membres de liste La fonction membre de liste pop_front() supprime le premier élément d'une liste. pop_back() supprime le dernier élément. La fonction membre erase() efface l'élément pointé par un itérateur. Il y a une autre fonction erase() qui peut effacer plusieurs éléments. /* || Effacer des objets d'une liste */ #include <list> # int main (void) { list<int> list1; // define a list of integers # /* || Mettre quelques nombres dans la liste || Elle contient maintenant 0,1,2,3,4,5,6,7,8,9 */ for (int i = 0; i < 10; ++i) list1.push_back(i); # list1.pop_front(); // effacer le premier élément 0 # list1.pop_back(); // effacer le dernier élément 9 # list1.erase(list1.begin()); // effacer le premier élément (1) en utilisant un itérateur # list1.erase(list1.begin(), list1.end()); // effacer tous les éléments restants # cout << "la liste contient " << list1.size() << " éléments" << endl; } En sortie, on aura : la liste contient 0 éléments 6.17 Suppression d'éléments d'une liste en utilisant la fonction membre de liste remove() La fonction membre de liste remove() efface les objets d'une liste. /* || Utilisation de la fonction membre de liste remove pour supprimer des éléments */ #include <string> #include <list> #include <algorithm> # PrintIt (const string& StringToPrint) { cout << StringToPrint << endl; } # int main (void) { list<string> Birds; # Birds.push_back("cockatoo"); Birds.push_back("galah"); Birds.push_back("cockatoo"); Birds.push_back("rosella"); Birds.push_back("corella"); # cout << "Liste originale avec le cacatoès" << endl; for_each(Birds.begin(), Birds.end(), PrintIt); # Birds.remove("cockatoo"); # cout << "Maintenant, sans le cacatoès" << endl; for_each(Birds.begin(), Birds.end(), PrintIt); } La sortie du programme sera : Liste originale avec le cacatoès cockatoo galah cockatoo rosella corella Maintenant, sans le cacatoès galah rosella corella 6.18 Suppression d'éléments d'une liste avec l'algorithme générique STL remove() L'algorithme générique remove() travaille d'une manière différente de la fonction membre de liste remove(). La version générique ne modifie pas la taille du conteneur. /* * Utilisation de l'algorithme générique remove pour supprimer des éléments d'une liste */ #include <string> #include <list> #include <algorithm> # PrintIt(string& AString) { cout << AString << endl; } # int main (void) { list<string> Birds; list<string>::iterator NewEnd; # Birds.push_back("cockatoo"); Birds.push_back("galah"); Birds.push_back("cockatoo"); Birds.push_back("rosella"); Birds.push_back("king parrot"); # cout << "Liste originale" << endl; for_each(Birds.begin(), Birds.end(), PrintIt); # NewEnd = remove(Birds.begin(), Birds.end(), "cockatoo"); # cout << endl << "Liste selon le nouvel itérateur indicateur de fin" << endl; for_each(Birds.begin(), NewEnd, PrintIt); # cout << endl << "Et maintenant, la liste originale, regardez bien !" << endl; for_each(Birds.begin(), Birds.end(), PrintIt); } La sortie du programme donne : Liste originale cockatoo galah cockatoo rosella king parrot Liste selon le nouvel itérateur indicateur de fin galah rosella king parrot Et maintenant, la liste originale, regardez bien ! galah rosella king parrot rosella king parrot L'algorithme générique remove() renvoie un itérateur indiquant un nouvel indicateur de fin de liste. L'espace entre le début de liste et la nouvelle fin (sans inclure cet élément) contient les éléments qui restent après suppression. Vous pouvez alors effacer l'espace entre la nouvelle fin de liste et l'ancienne en utilisant la fonction membre de liste erase. 6.19 Partitionner une liste avec l'algorithme générique stable_partition() et utilisation de la fonction membre de liste splice() Nous allons terminer avec un exemple légèrement plus compliqué. Il montre l'utilisation de l'algorithme générique stable_partition() et une variante de la fonction membre de liste splice(). Notez l'utilisation des objets fonctions et l'absence de boucles. Le contrôle passe à travers des séries d'instructions simples, qui sont des appels à des algorithmes STL. stable_partition() est une fonction intéressante. Elle réorganise les éléments de telle façon que ceux qui satisfont une certaine condition viennent avant ceux qui ne la satisfont pas. Elle préserve l'ordre relatif des deux groupes d'éléments. Un exemple éclaircira cela. La fonction splice() colle les éléments d'une autre liste dans la liste. Elle enlève ces éléments de la liste d'origine. Dans cet exemple, nous voulons prendre en compte quelques balises et quatre noms de fichiers d'une ligne de commande. Les noms de fichiers doivent apparaître dans l'ordre. En utilisant stable_partition() nous pouvons accepter les balises à n'importe quelle position par rapport aux noms de fichiers et les regrouper sans perturber l'ordre des paramètres noms de fichiers. Grâce aux algorithmes de comptage et de recherche disponibles nous pouvons déterminer, en appelant ces algorithmes, quelle balise a été positionnée plutôt que de toucher aux autres balises dans notre programme. J'ai trouvé que les conteneurs sont très pratiques pour gérer de petites quantités de variables dynamiques telles que celle-ci. /* || Utilisation de l'algorithme STL stable_partition || Accepte un nombre quelconque d'options sur la ligne de commande et || quatre noms de fichiers en ordre. */ #include <string> #include <list> #include <algorithm> # PrintIt ( string& AString ) { cout << AString << endl; } # class IsAFlag { public: bool operator () (string& PossibleFlag) { return PossibleFlag.substr(0,1)=="-"; } }; # class IsAFileName { public: bool operator () (string& StringToCheck) { return !IsAFlag()(StringToCheck); } }; # class IsHelpFlag { public: bool operator () (string& PossibleHelpFlag) { return PossibleHelpFlag=="-h"; } }; # int main (int argc, char *argv[]) { # list<string> CmdLineParameters; // les paramètres de la ligne de commande list<string>::iterator StartOfFiles; // début des noms de fichiers list<string> Flags; // liste des options list<string> FileNames; // liste des noms de fichiers # for (int i = 0; i < argc; ++i) CmdLineParameters.push_back(argv[i]); # CmdLineParameters.pop_front(); // nous ne voulons pas le nom du programme # // assurons-nous que nous avons les quatre noms de fichiers obligatoires int NumberOfFiles(0); count_if(CmdLineParameters.begin(), CmdLineParameters.end(), IsAFileName(), NumberOfFiles); # cout << "Un nombre " << (NumberOfFiles == 4 ? "correct " : "erroné ") << "(" << NumberOfFiles << ") de noms de fichiers a été spécifié" << endl; # // move any flags to the beginning StartOfFiles = stable_partition(CmdLineParameters.begin(), CmdLineParameters.end(), IsAFlag()); # cout << "Paramètres de ligne de commande après stable partition" << endl; for_each(CmdLineParameters.begin(), CmdLineParameters.end(), PrintIt); # // Regrouper toutes les options de la liste CmdLineParameters originale ien une liste d'options. Flags.splice(Flags.begin(), CmdLineParameters, CmdLineParameters.begin(), StartOfFiles); # if (!Flags.empty()) { cout << "Les options spécifiées étaient :" << endl; for_each(Flags.begin(), Flags.end(), PrintIt); } else { cout << "Aucune option n'a été spécifiée" << endl; } # // la liste de paramètres ne contient plus maintenant que des noms de fichiers. // Les regrouper en une liste de noms de fichiers. FileNames.splice(FileNames.begin(), CmdLineParameters, CmdLineParameters.begin(), CmdLineParameters.end()); # if (!FileNames.empty()) { cout << "Les fichiers suivants ont été spécifiés (dans l'ordre) :" << endl; for_each(FileNames.begin(), FileNames.end(), PrintIt); } else { cout << "Aucun nom de fichier n'a été spécifié" << endl; } # // regarder si l'option d'aide (help) a été spécifiée if (find_if(Flags.begin(), Flags.end(), IsHelpFlag())!=Flags.end()) { cout << "L'option d'aide a été spécifiée" << endl; } # // ouvrir les fichiers et faire ce que vous voulez # } Si l'on tape cette ligne de commande : test17 -w linux -o is -w great La sortie du programme sera : Un nombre incorrect (3) de noms de fichiers a été spécifié Paramètres de la ligne de commande après stable partition -w -o -w linux is great Les options spécifiées étaient : -w -o -w Les fichiers spécifiés (en ordre) étaient : linux is great 6.20 Conclusion Nous avons seulement effleuré ce que l'on peut faire avec une liste. Nous n'avons même pas traité le stockage d'une classe d'objets définie par l'utilisateur, bien que cela ne soit pas difficile. Si vous comprenez les concepts à la base des algorithmes présentés ci-dessus, vous ne devriez pas avoir de problèmes pour utiliser les autres. La chose importante avec STL, c'est d'avoir de bonnes bases. L'itérateur constitue la clé de STL. Les paramètres des algorithmes STL sont des itérateurs. Ces paramètres sont des domaines d'itérateurs, quelquefois un seul domaine, quelquefois deux. Les conteneurs STL fournissent les itérateurs. C'est pourquoi nous disons : list<int>::iterator, ou, list<char>::iterator, ou, list<string>::iterator. Les itérateurs sont dotés d'une hiérarchie bien définie. Ils ont différents pouvoirs. Certains itérateurs permettent un accès en lecture seulement à un conteneur, certains en écriture seulement. Certains ne peuvent se déplacer que vers l'avant, d'autres sont bi-directionnels. Quelques itérateurs permettent un accès direct à un conteneur. Les algorithmes STL demandent à l'itérateur de posséder un certain pouvoir. Si le conteneur ne fourni pas un itérateur ayant ce pouvoir, il ne sera pas possible de compiler l'algorithme. Par exemple, le conteneur de liste n'offre que des itérateurs bi-directionnels. L'algorithme générique sort() a besoin d'itérateurs permettant l'accès direct. C'est la raison pour laquelle nous avons besoin de la fonction spéciale membre de liste sort(). Pour vraiment utiliser STL correctement, il vous faut étudier soigneusement les différentes sortes d'itérateurs. Vous avez besoin de savoir que tels types d'itérateurs sont proposés par tels conteneurs. Vous avez alors besoin de savoir quels types d'itérateurs les algorithmes exigent. Vous avez besoin, naturellement, de comprendre de quels genres d'itérateurs vous pouvez disposer. 6.21 Utilisation de STL sur le terrain L'année dernière j'ai écrit pas mal de programmes commerciaux en C++ en utilisant STL. Dans tous les cas, grâce à cela, j'ai eu moins d'efforts à fournir et j'ai pratiquement éliminé toutes les erreurs de logique. Mon plus grand programme fait environ 5000 lignes. Sa vitesse est la chose probablement la plus remarquable. Il lit et traite de façon intensive un fichier de transactions de 1-2 Mb en environ vingt secondes. Il a été développé avec GCC 2.7.2 sous Linux et tourne maintenant sur une machine HP-UX. Il utilise environ 50 objets fonction et de nombreux conteneurs d'une taille allant de petites listes à un ensemble de plus de 14 000 éléments. Les objets fonction dans ce programme constituent une hiérarchie dans laquelle les objets fonction de plus haut niveau appellent celles de niveaux inférieurs. J'ai utilisé les algorithmes STL for_each(), find(), find_if(), count() et count_if() intensivement. J'ai pratiquement réduit mon programme à un ensemble d'appels à des algorithmes STL. STL a tendance à organiser automatiquement mon code en parties commande et ressources distinctes. En façonnant soigneusement les objets fonction et en leur donnant des noms ayant un sens, j'ai réussi à les faire passer au second plan et à me concentrer sur l'organisation de mon logiciel. Il y a beaucoup plus à savoir sur la programmation STL et j'espère que vous aurez pris plaisir à travailler ces exemples. Les pages d'errata pour les deux livres cités en bibliographie jouissent d'une activité importante sur le web et donc, vous pourrez les maintenir à jour. Le livre de Stroustrup dispose d'une excellente section de conseils, spécialement pour les débutants, à la fin de chaque chapitre. Le style général du livre est beaucoup plus celui d'une conversation que dans les éditions précédentes. Il est aussi plus volumineux. Il y a naturellement de nombreux livres sur STL chez les libraires. Regardez et voyez ce que vous pouvez trouver. 6.22 Bibliographie The STL Tutorial and Reference Guide, David Musser and Atul Saini. Addison Wesley 1996. The C++ Programming Language 3e, Bjarne Stroustrup. Addison Wesley 1997. Copyright © 1998, Scott Field - Publié dans le n°34 de la Linux Gazette. Adaptation française de Albert-Paul Bouillot Page suivante Page précédente Table des matières