Upload
najila
View
26
Download
0
Embed Size (px)
DESCRIPTION
Licence Informatique Besançon Méthode et Outils pour la Programmation Françoise Greffier. Bibliothèque standard du C++. STL. Intérêt Généricité Implantation dynamique d ’une pile surcharge de l ’opérateur = surcharge du constructeur par copie Implantation : chaînage arrière. - PowerPoint PPT Presentation
Citation preview
Bibliothèque standard du C++
Licence InformatiqueBesançon
Méthode et Outils pour la Programmation
Françoise Greffier
STL
IntérêtGénéricitéImplantation dynamique d ’une pile
surcharge de l ’opérateur = surcharge du constructeur par copie
Implantation : chaînage arrière
Des structures de données classiques
La bibliothèque standard (Standard Template Library : STL) fournit au programmeur des classes prédéfinies qui offrent des structures de données classique, associées à leurs opérations classiques.
Facteurs de qualité des logiciels :
• Fiabilité : écrite par des spécialistes (Andrew Koenig)• Réutilisabilité : portabilité• Compréhensabilité et facilité de maintenance
=> EFFICACITE
Exemple :Fusionner deux listes en les triant et placer le résultat dans un fichier se code en deux lignes.
Développer rapidement des applications en assemblant des briques des classes génériques.
Des composants réutilisables
Conteneurs (template)
Il existe deux grandes catégories de conteneurs :• Les séquences élémentaires (appelées aussi stockages élémentaires).Les dérivées des séquences élémentaires (appelées aussi types abstraits de données : TDA)• Les conteneurs associatifs (clé,valeur)
Pour comprendre les conteneurs proposés dans la STL, on doit appréhender à la fois les structures de données, les algorithmes associés et les itérateurs.
http://www.sgi.com/tech/stl/
Chaque conteneur possède possède des avantages et des inconvénients qui peuvent être appréhendés selon ces critères :• coût des insertions/suppressions• coût des accès aux éléments
Des composants réutilisables
On choisira un conteneur en cherchant à minimiser la somme des coûts des opérations les plus fréquentes effectués sur ceux-ci.
=> voir la complexité des algorithmes (opérations)
Les séquences
On distingue trois séquences : •vector (tableau)•list (liste)•deque (liste à accès préférentiels au premier et dernier)
Une séquence est un conteneur dans lequel les éléments sont organisés linéairement (il y a un premier, un suivant … , un dernier).
# include <vector.h># include <iostream.h>using namespace std;int main (void) {vector<int> v; V1.push_back(1); V1.push_back(2);V1.push_back(3);vector<int> v2(3); v2[0] = 1, v2[1] = 2; v2[2] =3;
if (v1==v2) cout << " OK " ;
else cout << " ???? (stupeur) ";
return 0; }
Les vecteurs # include <vector.h>
Les séquences : opérations communes
Méthodes disponibles sur tout conteneur :
• Gestion de la taille du conteneur
- size_type size() const;- size_type max_size() const;- bool empty() const;- void resize(size_type, T c=T());• Accès aux éléments :
- const_reference front() const;- const_reference back() const;
Les séquences : opérations communesMéthodes disponibles sur tout conteneur :
• Insertion des éléments
- void push_back(const T&);appel du constructeur par copie- .. . insert (...); avec un itérateur• Suppression d ’éléments :
- void pop_back();- .. . erase (...); avec un itérateur Echange d ’éléments :
- void swap(sequence<T>&);
Les séquences : opérations communesMéthodes disponibles sur tout conteneur :
Echange d ’éléments :
- void swap(sequence<T>&);Sequence est à remplacer par vector, list ou deque.Echange this avec les éléments du conteneur passé en argument.Pour échanger des éléments de séquences différentes, il faut passer à une version avec itérateur
Les vecteurs
Principales opérations (n est la dimension du vecteur)
• Sélecteur => capacité mémoire réservée donnée en nombre d ’élémentssize_type capacity() const;
Rqe : la taille est donnée par size (=> nb d ’éléments)
• Sélecteur : accès indexé : [ ] 0(1)reference operator[](size_type)
Les vecteurs
Principales opérations (n est la dimension du vecteur)
•Ajout ou suppression d ’un élément en fin de vecteur sans redimensionnement 0(1) push_back
• Ajout ou suppression d ’un élément en fin de vecteur avec redimensionnement 0(n) push_back
• Ajout ou suppression d ’un élément au milieu du vecteur 0(n)
Les conteneurs associatifs
Contrairement aux séquences, les conteneurs associatifs peuvent identifier leurs éléments par la valeur d ’une clé. Cette clé a parfois pour valeur une partie de la valeur de l ’élément.
Ces conteneurs sont particulièrement adaptés dans des applications où l ’on doit rechercher des éléments connaissant leur clé.
Un conteneur associatif offre la possibilité de rechercher rapidement les éléments mémorisés par leur clé.
Les conteneurs associatifs
Ces conteneurs sont « paramétrés » avec le type de la clé correspondant. .
Opérations sur les clés :recherche : find (complexité logarithmique)Comptage selon la clé : count
On doit avoir une relation d ’ordre total sur les clés
Les conteneurs associatifs
On trouve quatre conteneurs associatifs• set : clé = valeur de l ’élément• multiset : set avec occurrences multiples• map : élément = (clé,v)•multimap : map avec occurrences multiples sur clé
Opérations utilisant les clés :recherche : find (complexité logarithmique)Comptage selon la clé : count