Programmation II : [5pt] Cours d'introduction à la ... · Cours d’introduction à la programmation orientée objet ... par des opérateurs propres,sans forcément en connaître

Objectifs

S.D.A.

Listes

Piles

Bibliothèquestandard

Containers

Algorithmes etmaths

Conclusion

©EPFL 2018Jean-Cédric Chappelier& Jamila Sam

Programmation II :

Cours d’introduction à la programmation orientée objet

Structures de données abstraites et Bibliothèques

Jean-Cédric Chappelier

Laboratoire d’Intelligence ArtificielleFaculté I&C

Programmation II – S.D.A. et Bibliothèques – 1 / 59

Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Objectifs des 2 derniers cours

L’objectif de ces 2 derniers cours est :

1. de vous présenter (sommairement) un certain nombre d’outils standards existanten C++

Le but ici n’est pas d’être exhaustif, mais simplement de vous :I informer de l’existence des principaux outilsI faire prendre conscience d’aller lire/chercher dans la documentation les éléments

qui peuvent vous être utiles

2. de compléter le cours d’ICC du premier semestre sur un point qui (à mon avis) luimanquait :les structures de données abstraites :I listes chaînéesI piles


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Pourquoi modéliser les données?

L’élaboration d’un algorithme est grandement facilitée par l’utilisation de structures dedonnées abstraites, de plus haut niveau, et de fonctions de manipulations associées.

Une structure de données doit modéliser au mieux les informations à traiter pour enformaliser les traitements (complément des algorithmes)

Choisir les bons modèles de données fait partie du choix de bons algorithmes :algorithmes et structures de données abstraites sont intimement liés


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


C’est quoi une « structure de données abstraite »?Une structure de données abstraite (S.D.A.) est un ensemble organiséd’informations (ou données) reliées logiquement et pouvant être manipulées nonseulement individuellement mais aussi comme un tout.

Exemples généraux :

tableau (au sens général du terme)contenu : divers éléments de types à préciserinteractions : demander la taille du tableau, accéder (lecture/écriture) àchaque élément individuellement, ...

vecteur (au sens général, pas C++) : formalisation mathématique d’espacevectoriel sur un corps Kcontenu : n coordonnées (éléments de K )interactions : les propriétés élémentaires définissant un espace vectoriel


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


C’est quoi une « structure de données abstraite »?Une structure de données abstraite (S.D.A.) est un ensemble organiséd’informations (ou données) reliées logiquement et pouvant être manipulées nonseulement individuellement mais aussi comme un tout.

Exemple informatique élémentaire :

Vous connaissez déjà des structures de données abstraites, très simples : les typesélémentaires.

Par exemple, un intinteractions : affectation, lecture de la valeur, +, -, *, /


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Spécifications desstructures de données abstraites

Une S.D.A. est caractérisée par :I son contenuI les interactions possibles (manipulation, accès, ...)

Du point de vue informatique, une structure de données abstraite peut être spécifiée àdeux niveaux :

I niveau fonctionnel / logique : spécification formelle des données et desalgorithmes de manipulation associés

I niveau physique (programmation) : comment est implémentée la structure dedonnées abstraite dans la mémoire de la machine

+ déterminant pour l’efficacité des programmes utilisant ces données.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Spécifications des S.D.A. [2]

Au niveau formel (modèle), on veut généraliser cette idée « d’objets » manipulablespar des opérateurs propres, sans forcément en connaître la structure interne et encoremoins l’implémentation.

Par exemple, vous ne pensez pas un int comme une suite de 32 bits, mais biencomme un « entier » (dans un certain intervalle) avec ses opérations propres : +, -, *, /

Une structure de données abstraite définit une abstraction des données et cache lesdétails de leur implémentation.

abstraction : identifier précisément les caractéristiques de l’entité (par rapport à sesapplications), et en décrire les propriétés.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Spécifications des S.D.A. [3]

Une structure de données abstraite modélise donc l’« ensemble des services »désirés (interface) plutôt que l’organisation intime des données (détailsd’implémentation)

On identifie usuellement 4 types de « services » :1. les modificateurs, qui modifient la S.D.A.2. les sélecteurs ou accesseurs, qui permettent « d’interroger » la S.D.A.3. les itérateurs, qui permettent de parcourir la structure4. les constructeurs (pour l’initialisation)

Exemple : tableau dynamiquemodifieur : ajout d’un élément (push_back(a))sélecteur : lecture d’un élément (t[i])sélecteur : le tableau est-il vide? (t.empty())itérateur : index d’un élément ([i] ci-dessus)


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Divers exemples de S.D.A.

Il y a beaucoup de structures de données abstraites en Informatique :I tableaux (de toutes sortes, cf MOOC 1er semestre)I listesI pilesI files d’attente (avec ou sans priorité)I tables associatives (dites « de hachage »)I multi-listesI arbres (pleins de sorte...)I graphes

Beaucoup sont offertes dans les bibliothèques de C++.Vous avez déjà vu :I les tableaux (de taille fixe, dynamiques) ;I les chaînes de caractères.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Divers exemples de S.D.A.

Dans ce cours, nous n’allons tout d’abord détailler les deux plus fondamentales aprèsles tableaux :I les listesI et les piles

puis nous en présenterons rapidement d’autres, ainsi que d’autres aspects desbibliothèques de C++.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Liste chaînées

Les listes chaînées sont, comme les tableaux dynamiques, des SDA séquentielles,c’est-à-dire stockant des séquences d’éléments.

Par contre dans une liste chaînée, l’accès direct à un élément n’est pas possible,contrairement aux tableaux dynamiques.

Spécification logique :Ensemble d’éléments successifs (sans d’accès direct), ordonnés ou non

Interactions :I accès au premier élément (sélecteur)I accès à l’élément suivant d’un élément (sélecteur)I modifier l’élément courant (modificateur)I insérer/supprimer un élément après(/avant) l’élément courant (modificateur)I tester si la liste est vide (sélecteur)I parcourir la liste (itérateur)


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Listes

Exemple concret :

visionneuse stéreo (essayezd’accéder à la 3e image directe-ment, sans passer par la 2e !)

Exemple informatique :( a ( b ( c (d ()))))

a b c d 0

Une liste peut être vu comme une structure récursive :

liste = valeur + liste OU liste = vide


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Réalisations d’une listeI réalisation statique :

tableau (mais inconvénients ci-après)

I réalisation dynamique (liste chaînée) :

vector (mais inconvénient 1 ci-après)

ou

classe :class Element;typedef Element* ListeChainee;

class Element {private:

type_el valeur;ListeChainee suite;

};

Note : Ce « truc » (prédéclaration), utilisé ici pour clarifier les concepts, est très utile en cas dedépendances cycliques entre données : A utilise des (pointeurs sur des) Bs lesquels utilisent des(pointeurs sur des) As.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Pourquoi les listes dynamiques?

Les tableaux sont un type de données très utile en programmationmais présentent 2 limitations :

1. les données sont contiguës (les unes derrières les autres)et donc l’insertion d’un nouvel élément au milieu du tableau demande la recopie(le décalage) de tous les éléments suivants.=⇒ insertion en O(n)

2. pour les tableaux statiques, augmenter la taille (par exemple si elle n’est pasconnue a priori) nécessite la création d’un nouveau tableau=⇒ O(n)


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Complexité optimale des opérations élémentaires

Liste tableauaccès à un élément précis : O(n) O(1)

insérer un élément : O(1) O(n)

supprimer un élément : O(1) O(n)

parcourir la S.D.A. : O(n) O(n)

calculer la longueur : O(n) O(n)(voire O(1) si le stockage de cette valeur est effectué, en particulier si« longueur » a été spécifiée dans les « services » de la SDA.C’est par exemple le cas pour le vector et les array où size() est O(1).Ce n’est pas forcément le cas pour list ou forward_list car avoirsize() en O(1) peut avoir d’autres conséquences ; et ce ne serait entout cas plus une liste chaînée telle que décrite dans ce cours !)


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Listes chaînées en C++

Les listes (simplement) chainées existent depuis dans la bibliothèqueforward_list.

Note : Les listes doublement chainées existent depuis C++98 : list

(quelques) méthodes des listes chaînées :Type& front() retourne le premier élément de la listevoid push_front(Type) ajoute un élément en tête de listevoid pop_front() supprime le premier élémentvoid insert(iterator, Type) insertion avant un élément de

la liste désigné par un itérateur

Exemple : #include <forward_list>

forward_list<int> ma_liste({ 6, 1, 5, -23, 3 });

for (auto element : ma_liste) {cout << element << endl;

}

ma_liste.push_front(877);


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Piles

Spécification :Une pile est une structure de données abstraite dynamique contenant des élémentshomogènes (de type non précisé) à 1 point d’accès et permettantI d’ajouter une valeur à la pile (empiler ou push) ;I de lire la dernière valeur ajoutée ;I d’enlever la dernière valeur ajoutée (dépiler ou pop) ;I de tester si la pile est vide.

On ne « connaît » donc de la pile que le dernier élément empilé (son sommet).

Exemples concrets :

I une pile d’assiettesI une tour dans le jeu des tours de Hanoï


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Piles : exemple d’utilisation

empiler x x

empiler aax

dépiler x

empiler bbx

empiler yybx

dépilerbx


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Exemples d’utilisation des pilesLe problème des parenthèses : étant donnée une expression avec des parenthèses,est-elle bien ou mal parenthésée?

((a+b)∗c− (d +4)∗ (5+(a+c)))∗ (c+(d +(e+5∗g)∗ f )∗a)(correct)

(a+b)((incorrect)

Encore un peu plus complexe : différentes parenthèsesExemple avec [ et (

([])[()(()[])] + correct([)] + incorrect

Autres exemples d’utilisation des piles (non traités ici) :I tours de HanoïI notation postfixée (ou « polonaise inverse ») :

4 2 + 5 ∗(+ 5∗ (4+2))


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Vérification de parenthésage

Tant que lire caractère cSi c est ( ou [

empiler cSinon

Si c est ) ou ]Si pile vide

ÉCHECSinon

c′← lire la pileSi c et c′ correspondent

dépilerSinon

ÉCHECSi pile vide

OKSinon

ÉCHEC

Exemple

Entrée : ([)]

empile ( (

empile [[(

lu = ), top = [→ ne correspond pas=⇒ ERREUR


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Deuxième ExempleEntrée : ([()])

empile ( (

empile [[(

empile (([(

lu )→ correspond =⇒ dépile[(

lu ]→ correspond =⇒ dépile (

lu )→ correspond =⇒ dépile

pile vide =⇒ OK


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Piles (et files) en C++

Pour utiliser les piles en C++ : #include <stack>

Les files d’attente sont des piles où c’est le premier arrivé (empilé) qui est dépilé lepremier. Elles sont définies dans la bibliothèque <queue>.

Une pile de type type se déclare par stack<type> et une file d’attente parqueue<type>. Par exemple :

stack<double> une_pile;queue<char> attente;

Méthodes : Type top() accède au premier élément (sans l’enlever)void push(Type) empile/ajoutevoid pop() dépile/supprimebool empty() teste si la pile/file est vide


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Code C++ de l’exemple#include <stack>

// ...

bool check(string const& s) {stack<char> p;for (auto const& c : s) {

if ((c == '(') or (c == '['))p.push(c);

else if (c == ')') {if ((not p.empty()) and (p.top() == '('))

p.pop();else

return false;} else if (c == ']') {

if ((not p.empty()) and (p.top() == '['))p.pop();

elsereturn false;

}}return p.empty();

}


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Bibliothèque standard

La bibliothèque standard (d’outils) C++ facilite la programmation et permet de larendre plus efficace, si tant est que l’on connaisse bien les outils qu’elle fournit.

Cette bibliothèque est cependant vaste et complexe, mais elle peut dans la plupart descas s’utiliser de façon très simple, facilitant ainsi la réutilisation des structures dedonnées abstraites et des algorithmes sophistiqués qu’elle contient.

La bibliothèque standard est formée de 79 « paquets » :I 33 « classiques » (C++89)I 20 nouveaux ( )I les 26 bibliothèques C (C99)


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Contenu de la bibliothèque standard

La bibliothèque standard C++ contient 33 « paquets » de C++-98 :

<algorithm> plusieurs algorithmes utiles<bitset> gestions d’ensembles de bits<complex> les nombres complexes<deque> tableaux dynamiques avec push_front<exception> diverses fonctions aidant à la gestion des exceptions<fstream> manipulation de fichiers<functional> objets fonctions<iomanip> manipulation de l’état des flots<ios> définitions de base des flots<iosfwd> anticipation de certaines déclarations de flots<iostream> flots standards<istream> flots d’entrée<iterator> itérateurs<limits> diverses bornes concernant les types numériques<list> listes doublement chaînées<locale> contrôles liés au choix de la langue


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Contenu de la bibliothèque standard (2)

<map> tables associatives clé–valeur ordonnées<memory> gestion mémoire pour les containers<new> gestion mémoire<numeric> fonctions numériques<ostream> flots de sortie<queue> files d’attente<set> ensembles ordonnés<sstream> flots dans des chaînes de caractères<stack> piles<stdexcept> gestion des exceptions<streambuf> flots avec tampon (buffer)<string> chaînes de caractères<strstream> flots dans des chaînes de caractère [en mémoire]<typeinfo> information sur les types<utility> divers utilitaires<valarray> tableaux orientés vers les valeurs<vector> tableaux dynamiques


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion



La bibliothèque standard C++ contient 20 nouveaux « paquets » de :

<array> tableaux de taille fixe<atomic> expression atomique<chrono> heures et chronomètres<codecvt> conversions d’encodage de caractères<condition_variable> concurence (multi-thread)<forward_list> listes simplement chaînées<future> concurence (multi-thread)<initializer_list> listes d’initialisation<mutex> concurence (multi-thread)<random> nombres aléatoires<ratio> constantes rationnelles (Q)<regex> expressions régulières<scoped_allocator> allocation mémoire<system_error> erreurs système<thread> concurence (multi-thread)<tuple> n-uples<type_traits> caractéristiques de types


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion



<typeindex> utiliser les types comme index de containers<unordered_map> tables associatives non ordonnées<unordered_set> ensembles non ordonnés

Il existe aussi dans les outils standards les 26 « paquets» venant du langage C (C99) :

<cassert> test d’invariants lors de l’exécution<ccomplex> (inutile en C++) = <complex><cctype> diverses informations sur les caractères<cerrno> code d’erreurs retournés dans la bibliothèque standard<cfenv> manipulation des règles de gestion des nombres en vir-

gule flotante<cfloat> diverses informations sur la représentation des réels<cinttypes> int de taille fixée (C99)<ciso646> (inutile en C++)<climits> diverses informations sur la représentation entiers<clocale> adaptation à diverses langues<cmath> diverses définitions mathématiques<csetjmp> branchement non locaux


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion



<csignal> contrôle des signaux (processus)<cstdalign> (inutile en C++)<cstdarg> nombre variable d’arguments<cstdbool> (inutile en C++)<cstddef> diverses définitions utiles (types et macros)<cstdio> entrées sorties de base<cstdint> sous-partie de cinttypes<cstdlib> diverses opérations de base utiles<cstring> manipulation des chaînes de caractères à la C<ctgmath> <cmath> + <complex><ctime> diverses conversions de date et heures<cuchar> char de 16 ou 32 bits<cwchar> utilisation des caractères étendus<cwctype> classification des codes de caractères étendus


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Outils standards

On distingue plusieurs types d’outils.

Parmi les principaux :I les containers de baseI les containers avancés (appelés aussi « adaptateurs »)I les itérateursI les algorithmesI les outils numériquesI les traitements d’erreursI les chaînes de caractèresI les flots


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Outils standards (2)

Les outils les plus utilisés par les débutants sont :I les chaînes de caractères (string) 4

I les flots (stream) 4

I les tableaux dynamiques (vector) [container] 4

I les listes chaînées (list) [container avancé] 4

I les piles (stack) [container avancé] 4

I les algorithmes de tris (sort)I les algorithmes de recherche (find)I les itérateurs (iterators)


Objectifs

S.D.A.

Listes

Piles


Containersgénéralités

setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Plan

Présentons maintenant certains des outils standards de façon plus détaillée :

I set/unordered_set [container]

I iteratorI map/unordered_map [container]

I sortI findI complexI cmathI random


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Containers

Comme le nom l’indique, les containers sont des structures de données abstraites(SDA) servant à contenir (« collectionner ») d’autres objets.

Vous en connaissez déjà plusieurs : les tableaux, les piles, les files d’attentes (queue)et les listes chaînées.

Il en existe plusieurs autres, parmi lesquels les ensembles (set, unordered_set) et lestables associatives (map, unordered_map).

Les set permettent de gérer des ensembles au sens mathématique du terme (finis etordonnés) : collection d’éléments où chaque élément n’est présent qu’une seule fois.

Les tables associatives sont une généralisation des tableaux où les index ne sontpas forcément des entiers.

Imaginez par exemple un tableau que l’on pourrait indexer par des chaînes decaractères et écrire par exemple tab["Informatique"]


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Containers (2)

(Presque) Tous les containers contiennent les méthodes suivantes :

bool empty() : le containers est-il vide?

size_t size() : nombre d’éléments contenus dans le container(sauf forward_list)

void clear() : vide le container(sauf array, stack, queue et priority_queue)

iterator erase(it) : supprime du container l’élément pointé par it. it est unitérateur (généralisation de la notion de pointeur, voir quelques transparents plus loin)(sauf forward_list, array, stack, queue et priority_queue)

Ils possèdent également tous (sauf stack, queue et priority_queue) les méthodesbegin(), cbegin(), end() et cend() que nous verrons avec les itérateurs.


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Tableaux dynamiques : petit complémentPour accéder directement à un élément d’un tableau dynamique (vector) on utilisel’opérateur [] : tab[i].

Il existe une autre méthode pour cet accès : at(n) qui, à la différence de [n], lanceune l’exception out_of_range (de la bibliothèque <stdexcept>) si n n’est pas un indexcorrect.

Exemple :

#include <vector>#include <stdexcept>...vector<int> v(5,3); // 3, 3, 3, 3, 3int n(12);try {

cout << v.at(n) << endl;}catch (out_of_range) {

cerr << "Erreur : " << n << " n'est pas correct pour v"<< endl<< "qui ne contient que " << v.size() << " éléments."<< endl;

}


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Ensembles – ExempleLes ensembles (au sens mathématique) sont implémentés dans la bibliothèque <set>.Ils ne peuvent cependant contenir que des éléments du même type, lesquels sontordonnés par operator<.

(Pour des éléments de même type mais non ordonnés, i.e. sans operator<, on utilisera ununordered_set.)

On déclare un ensemble comme les autres containers, en spécifiant le type de seséléments, par exemple :set<char> monensemble;

Les ensembles n’étant pas des SDA séquentielles, l’accès direct à un élément n’estpas possible.

(quelques) méthodes des ensembles :

insert(Type) insère un élément s’il n’y est pas déjàerase(Type) supprime l’élément (s’il y est)find(Type) retourne un itérateur indiquant l’élément

recherché

À noter que la bibliothèque <algorithm> fournit des fonctions pour faire la réunion,l’intersection et la différence d’ensembles.


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Ensembles – Exemple

#include <set>...set<char> voyelles;

voyelles.insert('a');voyelles.insert('b');voyelles.insert('e');voyelles.insert('i');voyelles.erase('b');voyelles.insert('e'); // n'insere pas 'e' car il y est déjà

Comment parcourir cet ensemble?

for (size_t i(0); i < voyelles.size(); ++i)cout << voyelles[i] << endl;

ne fonctionne pas car c’est une SDA non-indexé (et même non-séquentielle).


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Ensembles – parcours

Comment parcourir cet ensemble?

En c’est facile :

for (auto const v : voyelles) {cout << v << endl;

}

Il y a aussi un autre moyen, plus avancé :

+ utilisation d’itérateurs


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Itérateurs

Les itérateurs sont une SDA généralisant d’une part des accès par index (SDAséquentielles) et d’autre part les pointeurs, dans le cas de containers.

Ils permettent :I de parcourir de façon itérative les containersI d’indiquer (i.e. de pointer sur) un élément d’un container

Il existe en fait 7 sortes d’itérateurs, mais nous ne parlons ici que de la plus générale,qui permet de tout faire : lecture et écriture du containers, aller en avant ou en arrière(accès quelconque en fait).


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Itérateurs (2)

Un itérateur associé à un container C<type> se déclare simplement commeC<type>::iterator nom;ou C<type>::const_iterator nom;si l’on ne modifie pas le container lors du parcours.

Exemples :

vector<double>::iterator i;set<char>::const_iterator j;

Il peut s’initialiser grâce aux méthodes begin() ou end() du container, voire d’autresméthodes spécifiques, comme par exemple find pour les containers non-séquentiels.

Exemples :

vector<double>::iterator i(monvect.begin());set<char>::iterator j(monset.find(monelement));

L’élément indiqué par l’itérateur i est simplement *i, comme pour les pointeurs.


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Retour sur l’exemple des ensembles

Pour parcourir notre ensemble précédent, nous devons donc faire :

for (set<char>::const_iterator i(voyelles.cbegin());i != voyelles.cend(); ++i) {

cout << *i << endl;}

Exemple d’utilisation de find :

set<char>::const_iterator i(voyelles.find('c'));if (i == voyelles.cend()) {

cout << "pas trouvé" << endl;} else {

cout << *i << " trouvé" << endl;}


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Code complet de l’exemple#include <set>#include <iterator>#include <iostream>using namespace std;

int main() {set<char> voyelles;

voyelles.insert('a');voyelles.insert('b');voyelles.insert('e');voyelles.insert('i');voyelles.insert('a'); // ne fait rien car 'a' y est déjàvoyelles.erase('b'); // supprime 'b'

// parcourt l'ensemblefor (auto const v : voyelles) cout << v << endl;

// recherche d'un élémentset<char>::const_iterator element(voyelles.find('c'));if (element == voyelles.cend())

cout << "je n'ai pas trouvé." << endl;else

cout << *element << " trouvé !" << endl;

return 0;}


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Suppression d’un élément d’un containerOn a vu que tout container possédait une méthode

iterator erase(it)

permettant de supprimer un élément, mais...

Attention ! On ne peut pas continuer à utiliser l’itérateur it !(plus exactement : erase rend invalide tout itérateur et référence situé(e) au dela du premierpoint de suppression)

Exemple d’erreur classique :

vector<double> v;...for (vector<double>::iterator i(v.begin()); i != v.end(); ++i)

if (cond(*i)) v.erase(i);

(avec bool cond(double);)n’est pas correct («Segmentation fault»)pas plus que :

for (vector<double>::iterator i(v.begin()); i != v.end(); ++i)if (cond(*i)) i =v.erase(i);


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Suppression d’un élément d’un container (2)Ce qu’il faut faire c’est :

vector<double>::iterator next;for (vector<double>::iterator i(v.begin()); i != v.end(); i = next) {

if (cond(*i)) { next = v.erase(i); }else { next = ++i; }

}

ou mieux en utilisant remove_if (ou remove) de <algorithm> :

v.erase(remove_if(v.begin(), v.end(), cond), v.end());

mais qui sont de toutes façons «coûteux» (O(v.size()2))

En effet, un tableau dynamique n’est pas la bonne SDA si l’on veut détruire un élément aumilieu et garder l’ordre (+ listes chaînées)

Note : si l’on ne tient pas à garder l’ordre, on peut toujours faire :

for (size_t i(0); i < v.size(); ++i)if (cond(v[i])) {

v[i] = v[v.size()-1];v.pop_back();--i;

}


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Tables associatives

Les tables associatives sont une généralisation des tableaux où les index ne sontpas forcément des entiers.

Imaginez par exemple un tableau que l’on pourrait indexer par des chaînes decaractères et écrire par exemple tab["Informatique"]

On parle d’« associations clé–valeur »

Les tables associatives sont définies dans la bibliothèque <map>.

Elles nécessitent deux types pour leur déclaration : le type des « clés » (les index) et letype des éléments indexé.

Par exemple, pour indexer des nombres réels par des chaînes de caractères ondéclarera :

map<string,double> une_variable;

Si l’ordre (operator<) des clés n’importe pas, on utilisera une unordered_map.


Objectifs

S.D.A.

Listes

Piles



setiteratorExemple

erasemap

Algorithmes etmaths

Conclusion


Tables associatives – exemple

#include <map>#include <string>#include <iostream>using namespace std;

int main() {map<string,double> moyenne;

moyenne["Informatique"] = 5.5;moyenne["Physique"] = 4.5;moyenne["Histoire des maths"] = 2.5;moyenne["Analyse"] = 4.0;moyenne["Algèbre"] = 5.5;

// parcours de tous les élémentsfor (map<string,double>::iterator i(moyenne.begin());

i != moyenne.end(); ++i)cout << "En " << i->first << ", j'ai " << i->second

<< " de moyenne." << endl ;

// recherchecout << "Ma moyenne en Informatique est de ";cout << moyenne.find("Informatique")->second << endl;

return 0;}


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Algorithmes

La bibliothèque algorithm (i.e. #include <algorithm>) fournit l’implémentation d’ungrand nombre d’algorithmes généraux :

I de séquencementquelques exemples : for_each, find, copy

I de trissort, mais aussi bien d’autres

I numériquesinner_product, partial_sum, adjacent_difference

I ...

3 exemples ici :I findI copy et les output_iteratorsI sort

pour les autres : référez-vous à la documentation


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


find

find est un algorithme général permettant de faire des recherches dans (une partied’)un container.Son prototype général est :

iterator find(iterator debut, iterator fin, Type valeur);qui cherche valeur entre debut (inclu) et fin (exclu). Il retourne un itérateur sur lecontenu correspondant à la valeur recherchée ou fin si cette valeur n’est pas trouvée.

Exemple :

list<int> uneliste;

uneliste.push_back(3);uneliste.push_back(1);uneliste.push_back(7);

list<int>::iterator result(find(uneliste.begin(),uneliste.end(), 7));

if (result != uneliste.end()) cout << "trouvé";else cout << "pas trouvé";cout << endl;


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


copy

copy est un algorithme général pour copier (une partir d’)un container dans un autre.

Son prototype général est :

OutputIterator copy(InputIterator debut, InputIterator fin,OutputIterator resultat);

qui copie le contenu compris entre debut (inclus) et fin (exclus) vers resultat (inclus)et les positions suivantes (itérateurs).

La valeur de retour est resultat + (fin - debut).

Attention ! Notez bien que cela copie des éléments, mais ne fait pas d’insertion : il fautabsolument que resultat ait (i.e. pointe sur) la place nécessaire !

Exemple :

copy(unensemble.begin(), unensemble.end(), untableau.begin());

Notez que l’on peut ainsi copier des données d’une SDA dans une autre SDA d’un autre type.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


copy (2)

copy peut être très utile pour afficher le contenu d’un container sur un flot en utilisantun ostream_iterator (je ne donne qu’un exemple ici :)

copy(container.begin(), container.end(),ostream_iterator<int>(cout, ", "));

container contenant ici des int, son contenu sera affiché sur cout, séparé par des ’,’.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


copy – Exemple complet

#include <iostream>#include <set>#include <vector>#include <iterator>using namespace std;

int main() {set<double> unensemble, unautre;

unensemble.insert(1.1); unensemble.insert(2.2);unensemble.insert(3.3);

// copy(unensemble.begin(), unensemble.end(), unautre.begin());// ne fonctionnerait pas ("assignment of read-only location")// car, ici, unautre n'a pas la taille suffisante.

vector<double> untableau(unensemble.size()); // prévoit la place

copy(unensemble.begin(), unensemble.end(), untableau.begin());

// outputcout << "untableau = ";copy(untableau.begin(), untableau.end(),

ostream_iterator<double>(cout, ", "));cout << endl;return 0;

}


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


sort

sort permet de trier des SDA implémentées sous forme de containers

La version la plus simple de tri est (il y en a d’autres) :void sort(iterator debut, iterator fin)

qui utilise operator< des éléments contenus dans la partie du container indiquée pardebut et fin(les objets qui y sont stockés doivent donc posséder cet opérateur)

Exemple :

list<double> uneliste;...sort(uneliste.begin(), uneliste.end());

Exemple plus avancé (qui affiche « 1 2 4 5 7 8 ») :

constexpr size_t N(6);int montableau[N] = { 1, 4, 2, 8, 5, 7 };sort(montableau, montableau + N);copy(montableau, montableau + N, ostream_iterator<int>(cout, " "));cout << endl;


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Nombres Complexes

La bibliothèque <complex> définit les nombres complexes.

Ils se déclarent par complex<double>. Ils possèdent un constructeur à 2 paramètrespermettant de préciser les parties réelle et imaginaire, e.g.

complex<double> c(3.2,1.4), i(0,1);

Par contre, il n’existe pas de constructeur permettant de créer un nombre complexe àpartir de ses coordonnées polaires.

En revanche, la fonction polar, qui prend comme paramètres la norme et l’argumentdu complexe à construire, permet de le faire. Cette fonction renvoie le nombrecomplexe nouvellement construit :

c = polar(sqrt(3.0), M_PI / 12.0);

Les méthodes des nombres complexes sont real() qui retourne la partie réelle,imag() qui retourne la partie imaginaire, et bien sûr les operateurs usuels.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Nombres Complexes (2)

Ce qui est plus inattendu c’est que les opérations de norme, argument, et conjugaisonn’ont pas été implémentées sous forme de méthodes, mais de fonctions :

double abs(const complex<double>&) retourne la norme (ausens français du terme) dunombre complexe

double norm(const complex<double>&) retourne le carré de lanorme

double arg(const complex<double>&) retourne l’argument dunombre complexe

complex<double> conj(const complex<double>&)retourne le complexe conjugué

La bibliothèque fournit de plus les extensions des fonctions de base (trigonométriques,logarithmes, exponentielle) aux nombres complexes.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Détails de <cmath>Quelques fonctions définies dans la bibliothèque <cmath> :abs valeur absolueacos arccosasin arcsinatan arctanceil dxe, entier supérieurcos coscosh cosinus hyperboliqueexp expfloor bxc, entier inférieurlog ln, logarithme népérienlog10 log, logarithme en base 10pow(x,y) xy = exp(y lnx) — (préférez la multiplication pour les faibles

puissances entières)sin sinsinh sinus hyperboliquesqrt √

tan tantanh tangente hyperbolique


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Détails de <cmath> (2)

Quelques constantes souvent fournies (mais non ISO) :e M_E

log2(e) M_LOG2E

log10(e) M_LOG10E

ln(2) M_LN2

ln(10) M_LN10

π M_PIπ

2 M_PI_2π

4 M_PI_41π

M_1_PI2π

M_2_PI2√π

M_2_SQRTPI√

2 M_SQRT21√2

M_SQRT1_2


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Nombres aléatoires

La génération de nombres au hasard sur ordinateur se fait avec des générateurs dit «pseudo-aléatoires » qui pour une valeur initiale donnée (appelée « graine » [« seed »en anglais]) donnent toujours la même séquence « aléatoire » (suivant une distributionde probabilité choisie).

Utiliser la même graine peut être utile pour déverminer un programme utilisant desnombres aléatoires.

Pour avoir une série de nombres aléatoires différente à chaque utilisation duprogramme, il faut utiliser une graine différente à chaque fois.

[Même si ce n’est pas terrible,] Cela se fait souvent en utilisant comme graine la valeur del’horloge de l’ordinateur à cet instant.

Une autre solution consiste à tirer la graine (voire la séquence elle-même) depuis unpériphérique matériel suffisement aléatoire (« random device ») :(micro-)déplacement de la souris, température du processeur, ...


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Nombres aléatoires (2)

Dans la bibliothèque <random> ( ), il existe différents générateurs de nombrespseudo-aléatoires et différentes distributions de probabilités.

Les deux doivent être combinés pour pouvoir effectuer une série de tirage.

Ci-après un exemple simple pour tirer de façon uniforme un nombre aléatoire entierentre min et max.


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Nombres aléatoires : exemple

#include <iostream>#include <functional> // pour bind()#include <random>using namespace std;

int main(){

// par exemple (dé ?)int min(1); int max(6);

// distribution uniforme entre min et maxuniform_int_distribution<int> distribution(min, max);

random_device rd; // utilisé ici pour la graineunsigned int graine(rd()); // par exemple, ou sinon de votre choix

// choix du générateur et initialisation (graine)default_random_engine generateur(graine);

auto tirage(bind(distribution, generateur)); // ésotérisme

for (unsigned int i(1); i <= 10; ++i) { // 10 tiragescout << tirage() << endl;

}return 0;

}


Objectifs

S.D.A.

Listes

Piles


Containers

Algorithmes etmaths

Conclusion


Ce que j’ai appris

I Les bases de la formalisation des données : les structures de donnéesabstraites

I Les deux structures de données abstraites les plus utilisées en informatique (enplus des tableaux et des types élémentaires) : les listes chaînées et les piles

I Qu’il existe beaucoup d’outils prédéfinis dans la bibliothèque standard de C++

Le but n’est évidemment pas de les connaître tous par cœur, mais de savoirqu’ils existent pour penser aller chercher dans la documentation les informationscomplémentaires.


Documents

Programmation II : [5pt] Cours d'introduction à la ... · Cours d’introduction à la programmation orientée objet ... par des opérateurs propres,sans forcément en connaître