View
104
Download
0
Category
Preview:
Citation preview
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20051
Cours n° 9Cours n° 9
Conception et Programmation à ObjetsConception et Programmation à ObjetsRéutilisation de composants Réutilisation de composants
de la bibliothèque standard du C++ (STL) de la bibliothèque standard du C++ (STL) 2/22/2
Equipe pédagogiqueEquipe pédagogiqueMarie-José Caraty, Denis Poitrenaud et Mikal ZianeMarie-José Caraty, Denis Poitrenaud et Mikal Ziane
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20052
Introduction
1. Conteneurs 1.1. Séquences élémentaires
Conteneurs vector, deque, list1.2. Adaptateurs de séquence
Conteneurs stack, queue, priority_queue1.3. Conteneurs associatifs
Conteneur map, set, multimap, multiset
2. Itérateurs
3. AlgorithmesManipulations - OrdonnancementRecherche - Ensemblistes
Conclusion
Sommaire
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20053
Conteneurs indexés par une clé de type quelconque et triés suivant cette clé (généralisation des séquences)
Concept de paire (clé, valeur) pour représenter un élément
set Clé et valeur sont confondues, éléments tous distincts
map
Clé et valeur sont distinctes, clé unique par élément
multiset
Plusieurs occurrences possibles du même élément
multimap
Une même clé peut correspondre à plusieurs éléments
1.3. CONTENEURS ASSOCIATIFS 1.3. CONTENEURS ASSOCIATIFS
IntroductionIntroduction
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20054
1.3. CONTENEURS ASSOCIATIFS 1.3. CONTENEURS ASSOCIATIFS
Méthodes communes des conteneurs associatifs (1/2)Méthodes communes des conteneurs associatifs (1/2)
bool empty();true si le conteneur est vide
size_type size() const;
Nombre d'éléments du conteneur
size_type max_size() const;
Contenance maximale du conteneur
size_type count(const key_T& k) const;
Nombre d’éléments de clé k
iterator lower_bound(const key_T& k) const;
Itérateur sur le 1er élément dont la clé est supérieure ou égale à k
iterator upper_bound(const key_T& k) const;
Itérateur sur le 1er élément dont la clé est inférieure ou égale à k
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20055
iterator find(const key_T& k);Recherche d’un élément de clé k
key_compare key_comp() const;Objet de type fonction binaire de comparaison de deux clés
value_compare value_comp() const;Objet de type fonction binaire de comparaison de deux valeurs
void erase(iterator i);Suppression de l’élément référencé par l'itérateur i
void erase(iterator debut, iterator fin); Suppression des valeurs de [debut fin[
void erase(const key_T& k); Suppression des valeurs de clé k
1.3. CONTENEURS ASSOCIATIFS 1.3. CONTENEURS ASSOCIATIFS
Méthodes communes des conteneurs associatifs (2/2)Méthodes communes des conteneurs associatifs (2/2)
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20056
pair <T1, T2> T1 : type du premier élément stocké dans la paireT2 : type du deuxième élément stocké dans la paire
Membres publics et fonction générique (externe) make_pairfirst membre correspondant au premier élément stockésecond membre correspondant au deuxième élément stocké
pair <T1, T2> make_pair (const T1& o1, const T2& o2);constitue un objet unique de type pair à partir de o1 et o2
Exemple :
type pair sur le concept (clé, valeur)décrivant un objet voiture
Pair<string, string> v;v = make_pair("Peugeot", "207 CC Coupé Cabriolet");Cout << "Marque :" << v.first << " Modèle :" v.second << endl;
clé (marque)
valeur (modèle)voiture
1.3. CONTENEURS ASSOCIATIFS 1.3. CONTENEURS ASSOCIATIFS
Patron (Patron (templatetemplate) de la classe ) de la classe pairpair
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20057
1.3. CONTENEURS ASSOCIATIFS - Conteneur MAP1.3. CONTENEURS ASSOCIATIFS - Conteneur MAP
Instanciation, propriétés et méthodes spécifiquesInstanciation, propriétés et méthodes spécifiques
map<key_T, value_T , Compare=less<key_T> > m;Déclaration d’un ensemble m de couples (clés de type key_T, valeurs associées de type value_T)pair make_pair(const key_T& k, const value_T& v)
Regroupement de la clé et de la valeur dans un seul élément
Insertion réussie si absence d’élément de même clé
Méthods spécifiquespair<iterator, bool> insert(const T& e);
Tentative d’insertion d’un élément e
pair<iterator, bool> insert(iterator i, const T& e);
Tentative d’insertion d’un élément e à l'emplacement spécifié par l'itérateur i (améloration du temps de recherche de l’emplacement)
void insert(iterator debut, iterator, fin)Tentative d’insertion des éléments de [debut fin[ d’une autre séquence
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20058
1.3. CONTENEURS ASSOCIATIFS - Conteneur MAP1.3. CONTENEURS ASSOCIATIFS - Conteneur MAP
ExempleExemple
#include <iostream>#include <map>#include <string>using namespace std;int main() {
map<string, float, less<string> > prixFruit; prixFruit.insert(make_pair("poire", 1.5));prixFruit.insert(make_pair("pêche", 2.7));prixFruit.insert(make_pair("orange", 1.2));map<string, float, less<string> >::iterator it;if ((it = prixFruit.find("poire")) == prixFruit.end())
cout << "fruit non référencé"; else cout << it->second;
}
Résultat d’exécution :1.5
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-20059
1.3. CONTENEURS ASSOCIATIFS - Conteneur SET1.3. CONTENEURS ASSOCIATIFS - Conteneur SET
Instanciation et propriétésInstanciation et propriétés
set<key_T, Compare=less<key_T> > s;Déclaration d’un ensemble s de clés de type key_T
Mêmes méthodes que pour le conteneur map
Clés et valeurs confondues
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200510
1.3. CONTENEURS ASSOCIATIFS - Conteneur MULTIMAP1.3. CONTENEURS ASSOCIATIFS - Conteneur MULTIMAP
Instanciation, propriétés et méthodes spécifiquesInstanciation, propriétés et méthodes spécifiques
multimap<key_T, value_T , Compare=less<key_T> > mm; Déclaration d’un ensemble mm de couples (clés de type key_T, valeurs associées de type value_T)
Pas d’échec d’insertion
Méthodes spécifiquesiterator lower_bound(const T& e);
Recherche du premier élément de clé k
iterator upper_bound(const T& e);
Recherche du dernier élément de clé k
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200511
1.3. CONTENEURS ASSOCIATIFS - Conteneur MULTIMAP1.3. CONTENEURS ASSOCIATIFS - Conteneur MULTIMAP
ExempleExemple
#include <iostream>#include <map>#include <string>using namespace std;int main() {
multimap<int, string, less<int> > conjug; conjug.insert(make_pair(1, "parler"));conjug.insert(make_pair(2, "choisir"));conjug.insert(make_pair(3, "prendre"));conjug.insert(make_pair(2, "finir"));conjug.insert(make_pair(1, "manger"));multimap<int, string, less<int> >::iterator it1, it2, it;it1 = conjug.lower_bound(2);it2 = conjug.upper_bound(2);cout << "Verbes du deuxième groupe : ";for (it = it1; it != it2; it++)
cout << it->second << ", "; }Résultat d’exécution :Verbes du deuxième groupe : choisir, finir
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200512
1.3. CONTENEURS ASSOCIATIFS - Conteneur MULTISET1.3. CONTENEURS ASSOCIATIFS - Conteneur MULTISET
Instanciation et propriétésInstanciation et propriétés
multiset<key_T, Compare=less<key_T> > ms;Déclaration d’un ensemble ms de clés de type key_ T
Mêmes opérations que pour le conteneur multimap
Clés et valeurs confondues
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200513
2. ITERATEURS2. ITERATEURS
Rôles des itérateursRôles des itérateurs
Variable qui repère la position d'un élément dans un conteneur
Utilisés pour accéder/balayer les éléments d'un conteneur Accès (lecture/écriture) des éléments du conteneur Balayage séquentiel de tous les éléments du conteneur
Méthodes membres des conteneurs (sauf adaptateurs) begin(), end() // Balayage du début du conteneur à sa fin rbegin(), rend() // Balayage de la fin du conteneur à son début
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200514
2. ITERATEURS2. ITERATEURS
Opérateurs associésOpérateurs associés
Généralisation et amélioration de la sûreté des pointeurs
Soit l’itérateur It
Déréférencement Accès au conteneur dont l'itérateur pointe l'élément
*It
Déplacement En avant, en arrière ou aléatoire
Exemples : ++It; It++; // balayage séquentiel avant--It; It--; // balayage séquentiel arrièreIt+=5; It-=3; // accès direct
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200515
2. ITERATEURS2. ITERATEURS
Hiérarchie des itérateursHiérarchie des itérateurs
Itérateur accès aléatoireLecture et écritureAccès aléatoire
Itérateur bidirectionnelLecture et écriture
Déplacement avant/arrière
Itérateur unidirectionnelLecture et écriture
Déplacement avant
Itérateur d'entréeLecture
Déplacement avant
Itérateur de sortieEcriture
Déplacement avant
InputIterator OutputIterator
RandomAccessIterator
BidirectionalIterator
ForwardIterator
<, <=, >, >=+, +=, -, -=
[]
*, i++, ++i Constructeur copie
Opérateur d'assignation==, !=
i--, --i
*, i++, ++iConstructeur copie
Opérateur d'assignation
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200516
2. ITERATEURS2. ITERATEURS
Déclaration des itérateursDéclaration des itérateurs
A chaque conteneur son type d'itérateurItérateur à accès aléatoire (vector et deque)Itérateur bidirectionnel (list, map, set)
Types membres des classes conteneursconst_iterator (version constante)iterator (version non constante)
Déclaration d’itérateurInstanciation du conteneur, opérateur de visibilité, type d’itérateur
Exemples de déclaration :Déclaration d'un itérateur Itv sur un vecteur d'entiersvector<int>::iterator Itv;
Déclaration d'un itérateur Itl sur une liste d'entierslist<int>::iterator Itl;
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200517
2. ITERATEURS2. ITERATEURS
Balayage/accès par itérateurBalayage/accès par itérateur
Affichage d'un conteneur vecteur d'entiers par balayage d'itérateur
typedef vector<int> vectInt;vectInt V;
// Première versionfor (vectInt::iterator It=V.begin(); It<V.end(); It++)
cout<<*It<<" "; // ou V[It]cout<<endl;
// Deuxième versionvectInt::iterator It=V.begin();while (It!=V.end()){
cout<<*It<<" "; ++It;}cout<<endl;
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200518
3. ALGORITHMES3. ALGORITHMES
ClassificationClassification
Manipulations Manipulations
Algorithmes
Recherche Recherche
Ordonnancement Ordonnancement Ensemblistes Ensemblistes
Comparaisons
Inclusion
Intersection
Union et fusion
Différence
Partitionnement
Copie
Echange
Remplacement
Réorganisation
Transformation
Tri
Gestion de tas
Recherche binaire
Motif
ElémentRemplissage
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200519
3. ALGORITHMES3. ALGORITHMES
Manipulation (Extraits)Manipulation (Extraits)
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
Copie de la séquence [first last[ à l’emplacement result
OutputIterator copy_backward(InputIterator first, InputIterator last, OutputIterator result);
Copie de la séquence ]last first] à l’emplacement result
ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
Echange des éléments des deux séquences [first1 last1[ et [first2 last2[
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
Initialisation de [first last[ par une fonction génératrice
void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last);
Echange des éléments des deux séquences [first middle[ et [middle last[
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200520
3. ALGORITHMES3. ALGORITHMES
Tris (Extraits)Tris (Extraits)
void sort (RandomAccessIterator first, RandomAccessIterator last [,Compare comp]);
Tri de la séquence [first last[ avec l’opérateur de comparaison Comp
void stable_sort (RandomAccessIterator first, RandomAccessIterator last [,Compare comp]);
Tri stable de la séquence [first last[ avec l’opérateur de comparaison Comp,
Ordre initial en cas d’égalité
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200521
3. ALGORITHMES3. ALGORITHMES
Recherches (Extraits)Recherches (Extraits)
InputIterator find(InputIterator first, InputIterator last, const T& v);
Recherche de la valeur v dans la séquence [first last[
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
Recherche d’une valeur de la séquence [first last[ satisfaisant pred
ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
Recherche d’une valeur de la séquence [first2 last2[ présente dans la séquence [first1 last1[
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 [, BinaryPredicate binary_pred]);
Recherche de la séquence [first2 last2[ dans la séquence [first1 last1[
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200522
Prérequis : l'opérateur == est défini pour T
template <class InputIterator, class T>
InputIterator find(InputIterator debut, InputIterator fin,
const T& valeur);
Recherche dans la séquence définie par l'intervalle [debut fin[
d'un item égal à valeurRetourne le premier itérateur i dans l'intervalle
tel que *i == valeurRetourne end() si la valeur n'est pas trouvée
3. ALGORITHMES3. ALGORITHMES
Opération de recherches Opération de recherches findfind
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200523
Prérequis : un prédicat pred est défini
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator debut, InputIterator fin,
Predicate pred);
Recherche dans la séquence définie par l'intervalle [debut fin[
d'un item égal à valeurRetourne le premier itérateur i dans l'intervalle tel que pred(*i) ==trueRetourne end() si le prédicat n'est pas satisfait
3. ALGORITHMES3. ALGORITHMES
Opération de recherche Opération de recherche find_iffind_if
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200524
template <class T>class PremierPlusGrand { // Objet fonction : classe avecprivate: // surcharge de l'opérateur ()
T x_;public:
PremierPlusGrand () : x_ (0) {}PremierPlusGrand (const T& x) : x_ (x) {}int operator () (const T& v) {return v > x_;}
};
vector <int> v; ... // Vecteur initialisé à 1 2 3 4 5
vector<int>::iterator i = find_if(v.begin(), v.end(), PremierPlusGrand <int> (3));
(i!=v.end()) ? cout<<*i : cout<<"element introuvable";
Résultat d'exécution : 4 (premier élément du conteneur >3)
3. ALGORITHMES3. ALGORITHMES
Exemple d’objet fonctionExemple d’objet fonction
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200525
3. ALGORITHMES3. ALGORITHMES
Ensemblistes (Extraits)Ensemblistes (Extraits)
set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result [,Compare comp]);
Union des deux ensembles [first1 last1[ et [first2 last2[ Résultat dans un troisième ensemble
set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
Intersection des deux ensembles [first1 last1[ et [first2 last2[ Résultat dans un troisième ensemble
set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
Différences entrel les deux ensembles [first1 last1[ et [first2 last2[ Résultat dans un troisième ensemble
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200526
Efficacité : objectif même des concepteurs (code efficace)
Complexité maximale spécifiée pour les méthodes/algorithmesAlgorithmes choisis pour l'implémentation des fonctionnalités sont les plus efficaces qui soient (les meilleurs connus à ce jour)
Gain en production de logiciel dû à la réutilisation Nombre impressionnant d'algorithmes disponibles Couverture de tous les besoins courants des programmeurs
Fiabilité : gain de fiabilité par réutilisation de composants Plus un composant est réutilisé, plus il est sûr
Réutilisation et maintenabilité : facilitée par la standardisation
Portabilité : a priori grâce à la norme ISO
Applicabilité des algorithmes aux structures de données utilisateur
3. ALGORITHMES3. ALGORITHMES
Avantages à utiliser STLAvantages à utiliser STL
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200527
#include <string>#include <map>#include <iterator>
using namespace std;
class Carnet {private:
map<string, string> MCarnet; //map(clé=nom, valeur=téléphone) map<string, string>::iterator it; //iterateur it pour accès
//et balayage de la mappublic:
Carnet() {}void ajoute(string nom, string tel); //ajoute un enregistrement
string getTel(string nom); //accesseur du numéro de téléphone string listeNom(string tel); //liste du/des nom(s)
string listeCarnet(); //liste du carnet complet};
ANNEXEANNEXE
Exemple – Exemple – Carnet téléphonique (Carnet.hpp)Carnet téléphonique (Carnet.hpp)
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200528
#include "Carnet.h"
using namespace std;
void Carnet::ajoute(string nom, string tel) {MCarnet[nom] = tel; //ajoute/remplace l'enregistrement
//correspondant à nom}
string Carnet::getTel(string nom) {it = MCarnet.find(nom); //fin de conteneur si aucune clé
//ne correspond à nomif (it == MCarnet.end()) return "";return (*it).second; //retourne le numéro de téléphone
}
ANNEXEANNEXE
Exemple – Exemple – Carnet téléphonique (Carnet.cpp)Carnet téléphonique (Carnet.cpp)
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200529
string Carnet::listeNom(string tel) {string resultat = "";for (it = MCarnet.begin(); it != MCarnet.end(); it++)
if ((*it).second == tel) resultat += (*it).first + '\n';return resultat;
}
string Carnet::listeCarnet() {string resultat;for (it = MCarnet.begin(); it != MCarnet.end(); it++)
resultat += (*it).first + " : " + (*it).second + "\n";return resultat;
}
ANNEXEANNEXE
Exemple – Exemple – Carnet téléphonique (Carnet.cpp)Carnet téléphonique (Carnet.cpp)
DUT2 – Conception et Programmation à Objets – Marie-José Caraty – 2004-200530
#include "Carnet.h" #include <iostream> using namespace std;void main() {
Carnet C;string dupond = "Dupond Georges";string telDupond = "0123456789";C.ajoute("Martin Pierre", "0122334455");C.ajoute(dupond, telDupond);C.ajoute("Dupond Jean", telDupond);C.ajoute("Durand Jacques", "0266778899");C.ajoute("Durand Jacques", "0266778800");
cout << C.listeCarnet() << endl;
cout << "Le numero de " << dupond << " est :";string numTel = C.getTel(dupond);if (numTel.length() == 0) cout << "inconnu" << endl;else cout << numTel << endl << endl;cout << "Entree(s) du no " << telDupond << " :\n" << endl;string liste = C.listeNom(telDupond);if (liste.length() == 0) cout << "aucune entree";else cout << liste << endl;
}
ANNEXEANNEXE
Exemple – Exemple – Carnet téléphonique (main.cpp)Carnet téléphonique (main.cpp)
Recommended