90
Structures de données IFT-2000 Abder Alikacem Abder Alikacem La librairie STL du C++ Département d’informatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Embed Size (px)

Citation preview

Page 2: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Utilisation des STL lib « list » lib « string» lib « stack» lib « algorithm » lib « queue» Concept de conteneur Adaptateur « priority_queue» lib « vector » lib « set » lib « deque» lib « multiset »

Plan

Page 3: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Utilisation des STL

Développée par Alexander Stepanov et Meng Lee chez HP Sont dans le domaine public.

Contiennent: les E/S, les chaînes, les conteneurs, les algorithmes les facilités numériques, les nombres complexes, la localisation

et des utilitaires généraux.

Page 4: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Utilisation des STL

Le standard C++ prévoit 32 en-têtes de bibliothèques C++.

<algorithm> <iomanip> <list> <ostream> <streambuf> <bitset> <ios> <locale> <queue> <string> <complex> <iosfwd> <map> <set> <typeinfo> <deque> <iostream> <memory> <sstream> <utility> <exception> <istream> <new> <stack> <valarray> <fstream> <iterator> <numeric> <stdexcept> <vector> <function> <limits>

Page 5: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Utilisation des STL

Le standard C++ prévoit 18 en-têtes de bibliothèques C.

<cassert> <ciso646> <csetjump> <cstdio> <ctime> <cctype> <climits> <csignal> <cstdlib> <cwchar> <cerrno> <clocale> <cstdarg> <cstring> <cwctype> <cfloat> <cmath> <cstddef>

Remarque: on peut écrire #include <cstdio> : espace de nommage « std » ou #include<cstdio.h> : pas d ‘espace de nommage

Page 6: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Utilisation des STL

Exercice

Compilez les codes suivant avec votre compilateur et concluez!

#include <iostream>

int main() {

cout << "hello world"<< endl;

return 0;}

#include <iostream>

using namespace std;

int main() {

cout << "hello world"<< endl;

return 0;}

Page 7: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

string s1;

string s2(hello world );

int i = s2.length();int j = s2.size();

string s3 = s2.substr(int pos, int len);

s2.insert(int pos, char *txt);

Lib « string »

Création d’objets

Longueur

Extraction de sous-chaîne

Insertion

Page 8: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

s2.replace(int pos, int len, char *txt);

string s4 = s2 + s3;

s4 += s1; s4 += hello world

s4.erase(int pos, int len);

if (s4.empty()) {…}

Lib « string »

Remplacer des caractères

Concaténer

Supprimer

Chaîne vide ?

Page 9: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

if (s1>s2) {…}

cout << s2[2] << endl;

char * Cstr = s2.c_str();

Lib « string »

comparaison

Indexation

Accéder au char * à la C

Page 10: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

int max_size = s1.max_size();

int i = s2.capacity();

s2.resize(int new_size, char fill = 0);

s2.reserve(int size);

Lib « string »

Taille max sur le système

Quelle taille mémoire Effectivement utilisée?

Retailler

Réserve de la place

Page 11: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

size_t i = s1.find(char *txt);size_t i = s1.find(char *txt, int pos);

size_t i = s1.rfind(char *txt);size_t i = s1.rfind(char *txt, int pos);

if (i == s1.npos) {…}

Lib « string »

Recherche

Recherche « reverse »

Échec d’une recherche ?

Page 12: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

size_t i = s1.find_first_of(char *txt);

size_t i = s1.find_last_of(char *txt);

size_t i = s1.find_first_not_of(char *txt);

size_t i = s1.find_last_not_of(char *txt);

Lib « string »

Recherche parmi

Recherche dernier parmi

Recherche premier hors

Recherche dernier hors

Page 13: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

string s;cin >> s;

string s = hello worldcout << s << endl;

Lib « string »

Entrée

Sortie

Page 14: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

#include <string>using namespace std;

string:: const_iterator …

string::iterator …

Lib « string »

Itérateur constant

Itérateur « normal »

string s = "hello world"; cout << s << endl; for(string::iterator s_it = s.begin(); s_it != s.end(); s_it++) {

*s_it = (char) toupper(*s_it); }

cout << s << endl;

Page 15: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<string>

En cas d’erreur sur la position d’un caractère, la méthode appeléegénère une exception « out_of_range ».

Nous verrons les exceptions un peu plus loin!

Page 16: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Tri de tableaux par valeurs croissantes

Fonctionne si le type T possède l’opérateur « < « 

#include <algorithm>using namespace std;

sort(adresse 1er élément de type T, adresse fin de liste de type T);

const int N = 10;int tab[N];sort (&tab[0], &tab[N]);

Page 17: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Tri de tableaux avec fonction de « tri »

#include <algorithm>using namespace std;

sort(adresse 1er élément de type T, adresse fin de liste de type T, comparaison );

const int N = 10;int tab[N];inline bool compSup(int i, int j) { return i > j;}sort (&tab[0], &tab[N], compSup);

Page 18: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Mélange de tableaux (l’inverse du tri)

#include <algorithm>using namespace std;

random_shuffle(adresse 1er élément de type T, adresse fin de liste de type T );

const int N = 10;int tab[N];sort (&tab[0], &tab[N]);random_shuffle(&tab[0], &tab[N]);

Page 19: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Tri partiel de tableaux

#include <algorithm>using namespace std;

partial_sort(adresse 1er élément, adresse arrêt, adresse fin);partial_sort(adresse 1er élément, adresse arrêt, adresse fin, comparaison);

S’arrête dès que [1er …arrêt[ est trié

const int N = 10;int tab[N];inline bool compSup(int i, int j) { return i > j;}partial_sort(&tab[0], &tab[5], &tab[N], compSup);

Page 20: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Copie de tableaux

#include <algorithm>using namespace std;

copy(adresse 1er source, adresse arrêt source, adresse 1er destination);

const int N = 10;int tab[N], tab2[N];copy(&tab[0], &tab[N], &tab2[0]);

Page 21: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Partitionnement de tableaux

#include <algorithm>using namespace std;

partition(adresse 1er, adresse arrêt, critère);

const int N = 10;int tab[N];inline positive (int i) { return i>0;}partition(&tab[0], &tab[N], positive);

Page 22: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Rotation gauche de tableaux

#include <algorithm>using namespace std;

rotate(adresse 1er, adresse remplaçant, adresse arrêt);

const int N = 10;int tab[N];rotate(&tab[0], &tab[2], &tab[N]); // « deux pas à gauche »

Page 23: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Remplissage constant de tableaux

#include <algorithm>using namespace std;

fill(adresse 1er, adresse arrêt, valeur de type T);

const int N = 10;int tab[N];fill(&tab[0], &tab[N], 10); // remplir avec des 10

Page 24: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Remplacement d’une valeur par une autre dans un tableau

#include <algorithm>using namespace std;

replace(adresse 1er, adresse arrêt, valeur recherché, nouvelle valeur);

const int N = 10;int tab[N];replace(&tab[0], &tab[N], 10, 20); // remplacer des 10 par des 20

Page 25: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Remplacement des éléments avec fonction de calcul

#include <algorithm>using namespace std;

generate(adresse 1er, adresse arrêt, fonction de calcul);

const int N = 10;int tab[N];int paire() {static int start = 0; start += 2; return start -2;}generate(&tab[0], &tab[N], paire); // remplissage avec des//nombres paires croissants

Page 26: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Renverser l’ordre des éléments d’un tableau

#include <algorithm>using namespace std;

reverse(adresse 1er, adresse arrêt);

const int N = 10;int tab[N];reverse(&tab[0], &tab[N]);

Page 27: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Fusionner deux tableaux

#include <algorithm>using namespace std;

merge(adr 1er src1, adr arrêt src1, adr 1er src2, adr arrêt src2, adr 1er dest);

const int N = 10;int tab[N], tab2[N], TAB [2*N];merge(&tab[0], &tab[N], &tab2[0], &tab2[N], &TAB[0]);

Page 28: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Réduire un tableau en enlevant les doublons successifs

#include <algorithm>using namespace std;

nouvelle adr arrêt = unique (adr 1er, adr arrêt);

const int N = 10;int tab[N], tab2[N], TAB [2*N];merge(&tab[0], &tab[N], &tab2[0], &tab2[N], &TAB[0]);sort (&TAB[0], &TAB[2*N]);int * newstop = unique(&TAB[0],&TAB[2*N]);

Page 29: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Parcours séquentiel d’un tableau avec calcul

#include <algorithm>using namespace std;

transform (adr 1er, adr arrêt, adr 1er dest, calcul);

const int N = 10;int tab[N], tab2[N];inline int add1(int i) { return i+1;} // ajout de 1 à chaque élément transform(&tab[0], &tab[N], &tab2[0], add1);

Page 30: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Parcours séquentiel de deux tableaux avec calcul

#include <algorithm>using namespace std;

transform (adr 1er src1, adr arrêt src1, adr 1er src2, adr 1er dest, calcul);

const int N = 10;int tab[N], tab2[N], sum[N];inline int add(int i, int j) { return i+j;} // faire la somme transform(&tab[0], &tab[N], &tab2[0], &sum[0], add);

Page 31: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Échanger le contenu de deux tableaux

#include <algorithm>using namespace std;

swap_ranges (adr 1er src1, adr arrêt src1, adr 1er src2);

const int N = 10;int tab[N], tab2[N];swap_ranges(&tab[0], &tab[N], &tab2[0]);

Page 32: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Rechercher un élément dans un tableau

#include <algorithm>using namespace std;

find (adr 1er, adr arrêt, valeur de recherche);

Renvoie la position si trouvé, sinon adr arrêt

const int N = 10;int tab[N];// rechercher 0 find(&tab[0], &tab[N], 0);

Page 33: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Rechercher par fonction dans un tableau

Renvoie la position si trouvé, sinon adr arrêt

#include <algorithm>using namespace std;

find_if (adr 1er, adr arrêt, fonction de recherche);

const int N = 10;int tab[N];bool zero (int i) {return i == 0;}find_if(&tab[0], &tab[N], zero);

Page 34: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Rechercher deux valeurs adjacentes identiques dans un tableau

Renvoie la position si trouvé, sinon adr arrêt

#include <algorithm>using namespace std;

adjacent_find (adr 1er, adr arrêt);

const int N = 10;int tab[N];adjacent_find(&tab[0], &tab[N]);

Page 35: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Rechercher deux valeurs adjacentes ayant une propriété

Renvoie la position si trouvé, sinon adr arrêt

#include <algorithm>using namespace std;

adjacent_find (adr 1er, adr arrêt, propriété);

const int N = 10;int tab[N];bool egales (int i, int j) {return i == j;}adjacent_find(&tab[0], &tab[N], egales);

Page 36: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Compter le nombre d’occurrence d’une valeur

Renvoie le nombre d’occurences

#include <algorithm>using namespace std;

int count(adr 1er, adr arrêt, valeur de recherche);

const int N = 10;int tab[N];//nombres de valeurs nullesint n = count(&tab[0], &tab[N], 0);

Page 37: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Compter le nombre d’occurrence ayant une propriété

Renvoie le nombre d’occurences

#include <algorithm>using namespace std;

int count_if(adr 1er, adr arrêt, fonction de recherche);

const int N = 10;int tab[N];bool nulle (int i) {return i == 0;}//nombres de valeurs nullesint n = count(&tab[0], &tab[N], nulle);

Page 38: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Un « for » de plus…

#include <algorithm>using namespace std;

for_each(adr 1er, adr arrêt, fonction de calcul);

const int N = 10;int tab[N];void affiche (int i) {cout << i << endl;}//parcours et affichefor_each(&tab[0], &tab[N], affiche);

Page 39: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Un tableau A est il inclus dans un tableau B?

#include <algorithm>using namespace std;

bool includes (adr 1er B, adr arrêt B, adr 1er A, adr arrêt A);

const int N = 10;int A[N], B[2*N];//A est-il inclus dans Bbool b = inlcudes(&B[0], &B[2*N], &A[0], &A[N]);

Page 40: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

C = Union de A et B

#include <algorithm>using namespace std;

adr arrêt dst = set_union (adr 1er A, adr arrêt A, adr 1er B, adr arrêt B, adr 1er C);

const int N = 10;int A[N], B [N], C[2*N];// C = A union Bint * last = set_union(&A[0], &A[N], &B[0], &B[N], &C[0]);

Page 41: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Intersection de A et B

#include <algorithm>using namespace std;

adr arrêt dst=set_intersection(adr 1er A,adr arrêt A,adr 1er B,adr arrêt B,adr 1er C);

const int N = 10;int A[N], B [N], C[N];// C = A intersection Bint * last = set_intersection(&A[0], &A[N], &B[0], &B[N], &C[0]);

Page 42: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Différence de A et B (A-B)

#include <algorithm>using namespace std;

adr arrêt dst=set_difference(adr 1er A,adr arrêt A,adr 1er B,adr arrêt B);

const int N = 10;int A[N], B [N], C[N];// C = A - Bint * last = set_différence(&A[0], &A[N], &B[0], &B[N], &C[0]);

Page 43: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<algorithm>

Lib « algorithm »

Différence symétrique A et B ((A union B) – (A intersection B))

#include <algorithm>using namespace std;

adr arrêt dst=set_symmetric_difference(adr 1er A, adr arrêt A, …);

const int N = 10;int A[N], B [N], C[N];// C = (A B) – (A B)int * last = set_symmetric_difference(&A[0], &A[N], &B[0], &B[N], &C[0]);

Page 44: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Concept de conteneur

Les conteneurs sont des structures de données permettant de ranger en mémoire des ensembles de valeurs « copie constructibles ».

Le type tableau est un « conteneur », mais il y en a d’autres en C++ qui sont beaucoup plus génériques

1. Conteneurs séquentiels: vector<T>, deque<T>, list<T>

2. Conteneurs associatifs: set, multiset, map, multimap

Page 45: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<vector>

#include <vector>using namespace std;

const int N = 10;vector<int> t(N), T(N,0);

int i = 5;int j = t[i];

sort(&t[0], &t[N]);

vector<int>::interator it;for(it = t.begin(); it!=t.end(); it++) {…}

Lib « vector » vector est génériqueDéclaration

Indexation

<algorithm>

itérateurs

Page 46: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<vector>

#include <vector>using namespace std;

t.resize(x,y);

vector<int> u(2*N, 0);u=t;

t.clear();

int i = 1;t.insert(t.end(), i);

Lib « vector » Taille dynamique

copie

Effacer le contenu après t.clear() == 0

Insérer une valeur

Page 47: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<vector>

#include <vector>using namespace std;

sort(t.begin(), t.end());

t.swap(T)

t.erase(t.begin());

vector<int>::reverse_iterator rit;for(rit=t.rbegin(); rit!=t.rend(); rit++) {…}

Lib « vector » <algorithm> +itérateur

Permuter

Supprimer un élément

Itérateur inverse

Page 48: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<vector>

#include <vector>using namespace std;

int i = t.front();

int i = t.back();

t.pop_back();t.pop_front(); //NON

int i =1;t.push_back(i);t.push_front(i); //NON

Lib « vector » Accès au premier élément

Accès au dernier élément

Supprimer fin de liste

Insérer en fin de liste

Page 49: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<vector>

#include <vector>using namespace std;

int size = t.size();

int max_size = t.max_size();

int i =10;int j = t.at(i);

Lib « vector » Longueur de la liste

Longueur max dépend du système

Indexation + contrôle dynamique des bornes

Page 50: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<vector>

En cas d’erreur sur la position d’un élément, la méthode appelée génèreune exception « out of range ».

Nous verrons les exceptions plus loin!

Page 51: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<deque>

#include <deque>using namespace std;

deque<int> d;d.push_front(0);

d.pop_front();

Lib « deque » deque est générique

Toutes les méthodes de <vector> sont utilisables +

Insérer en tête

Supprimer en tête

Page 52: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<list>

#include <list>using namespace std;

Lib « list » list est générique

Ne supporte que les itérateurs bidirectionnels. Pas d’accès direct.[] et at() ne sont pas supportés par cette classe.

Les algorithmes qui nécessitent l’accès direct ne sont pas applicables.Par exemple, vector::sort().

De nouvelles méthodes et des implémentations spécifiques de certainsalgorithmes.

Page 53: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<list>

#include <list>using namespace std;

list<int> d;d.sort();

list<int> e;d.merge(e);

d.unique();

d.reverse();

d.remove(0);

Lib « list » list est générique

sort()

merge()

unique()

reverse()

remove()

Page 54: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<list>

#include <list>using namespace std;

d.splice(d.begin(), e);

Lib « list » list est générique

Combiner 2 listes

Cela ajoute la liste e avant l’élément pointé par l’itérateur. Après splice(), e est vide.

Page 55: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<stack>

#include <stack>using namespace std;

Lib « stack » stack est générique

Ne peut être instancié qu’à partir d’un des conteneurs suivants:<vector>, <deque> ou <list>.

Il suffit que le conteneur supporte les fonctions :back(), push_back() et pop_back().

C’est une PILE!

Page 56: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<stack>

#include <stack>using namespace std;

stack<int, vector<int> > s;

s.push(1);

s.pop();

int n = s.size();

Lib « stack » stack est générique

Déclaration (pile d’entiers)

Empiler

Dépiler

Taille de la pile

Page 57: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<stack>

#include <stack>using namespace std;

if(s.empty()){…}

int i = s.top();

Lib « stack » stack est générique

Pile vide?

Sommet de la pile

Page 58: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<queue>

#include <queue>using namespace std;

Lib « queue » queue est générique

Ne peut être instancié qu’à partir d’un des conteneurs suivants:

<list> ou <deque>

C’est une FIFO!

Page 59: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<queue>

#include <queue>using namespace std;

queue<int, list<int> > f;

int n =f.size();

f.push(10);

f.pop();

Lib « queue » queue est générique

Déclaration

Taille

Ajouter en tête

Supprimer en queue

Page 60: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<queue>

#include <queue>using namespace std;

int tete =f.front();

int fin = f.back();

Lib « queue » queue est générique

Tête de la file

Fin de la file

Page 61: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<priority_queue>

#include <priority_queue>using namespace std;

Lib « priority_queue » priority_queue est générique

C’est une liste avec un critère de tri automatique lors de l’inserstion.Le « plus grand » élément est en tête de liste.

Ne peut être instancié qu’à partir des conteneurs suivants:<vector> ou <deque>

A besoin d’un objet de type « fonction de comparaison »

Page 62: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<priority_queue>

#include <priority_queue>#include <functional>using namespace std;

priority_queue<int, vector<int>, greater<int> > q;

if(q.empty()) {…}

int size = q.size();

Lib « priority_queue » priority_queue est générique

Création

File vide?

Taille de la file

Page 63: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<priority_queue>

#include <priority_queue>#include <functional>using namespace std;

int i = 10;q.push(i);

q.pop();

int i = q.top();

Lib « priority_queue » priority_queue est générique

Ajouter un élément

Supprimer la tête (le + grand)

Obtenir tête de liste

Page 64: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<set>

#include <set>using namespace std;

Lib « set » set est générique

C’est un conteneur associatif. Il permet de stocker des objet ayant uneclé d’accès associatif unique.

Il peut être parcouru dans les deux sens.

Les objets sont classés selon une relation d’ordre sur les clés.

Page 65: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<set>

#include <set>using namespace std;

set<int, less<int> > s;

set<int, less<int> >::iterator it;set<int, less<int>

>::const_iterator cit;for(it=s.begin(); it!=s.end(); it++)

{…}

int i = 22;s.insert(i);

Lib « set » set est générique

Création

Itérateur

Insertion

Page 66: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<set>

#include <set>using namespace std;

pair<set<int, less<int> > ::iterator, bool> p;

p = s.insert(22);if(p.second) {…} //erreur

s.erase(22);

set<int, less<int> >::iterator it;…s.erase(it);

Lib « set » set est générique

Détection insertion double

Éliminer un élément d’après sa valeur

Éliminer un élément d’après sa position

Page 67: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<set>

#include <set>using namespace std;

set<int, less<int> > ::iterator it;it = s.find(22);if(it != s.end()) {…} //trouvé

set<int, less<int> > ::iterator it;it = s.lower_bound(22);

set<int, less<int> >::iterator it;it = s.upper_bound(22);

Lib « set » set est générique

Recherche d’une valeur

Recherche de la première valeursupérieure ou égale

Recherche de la première valeursupérieur

Page 68: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<multiset>

#include <multiset>using namespace std;

multiset<int, greater<int> > m;

int n = m.erase(22);

Lib « set » multiset est générique

Comme « set » mais les clés peuvent apparaître plusieurs fois.

création

Erase renvoie le nombre d’objets retirés

Page 69: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<map>

Lib « map » est un conteneur associatif quasiment identique au « set » à cecisauf que la clé fait partie de l’élément stocké dans le « map ».

Les fonctions définies pour les « set » s’appliquent également aux « map ».

Page 70: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<map>

#include <map>using namespace std;

class A {public : int i; float f;

A(int j, float g): i(j), f(g) {}};typedef map<int, A, less<int> >

mapA;typedef mapA::value_type

mapA_item;

#include <utility>` int a =1; float b =1.0;

mapA_item mAi = make_pair(a, A(a,b));

int i = mAi.first; A aa = mAi.second;

Lib « map »

Création

Value_type est une « paire » <type cl, type donnée>

Page 71: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<map>

#include <map>using namespace std;

mapA mA;mA.insert(mAi);mA[1].f +=2.0;

Lib « map »

Accès direct à un élément

Page 72: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<multimap>

#include <multimap>using namespace std;

Lib « multimap »

Le « multimap » est au « map » ce que le « multiset » sont au « set ».

Page 73: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Objets de type fonction

#include <functional>using namespace std;

Les objets fonctions sont définis dans la bibliothèque « functional »

Tout objet fonction doit fournir une implémentation de l’oprateuroperator(), c’est-à-dire une surdéfinition de l’appel de fonction.

C’est un concept qui permet de remplacer les pointeurs sur des fonctionsPar des noms de classes qui implémentent l’opérateur operator ().

Page 74: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Objets de type fonction

Comparaisons equal_to, not_equal_to, greater, less, greater_equal, less_equal

Opérations logiques logical_and, logical_or, logical_not

Négateurs unary_negate, binary_negate, not1, not2

Lieurs binder1st, bind1st, binder2nd, bind2nd

Adaptateurs pointer_to_unary_function, pointer_to_binary_function, ...  

Opérations arithmétiques plus, minus, multiplies, divides, modulus

Page 75: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Objets de type fonction

#include <functional>

multiplies<int> my_mult;

int i = 2;int j = 4;

cout << my_mult(i,j) << endl;

template <class T> class my_mult {public:

T operator() (T a, T b){return a*b;

}};

float i = 2.0;float j = 4.0;cout << my_mult<float>(i,j) << endl;

Page 76: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Création

Taille du valarray

Parcours

#include <valarray>using namespace std;

const int nb_elem = 10;valarray<double> v(nb_elem);

cout << v.size() << endl;

for(int i = 0; i < v.size(); i+++v[i] = i*1.5;

Page 77: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Minimum et maximum

Somme des éléments

#include <valarray>using namespace std;

cout << v.min() << endl;cout << v.max() << endl;

cout << v.sum() << endl;

Page 78: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Affichage

#include <valarray>using namespace std;

template<class T> ostream& operator<<(ostream& o, const valarray<T>& v) {

for(int i=0;i<v.size();i++)o<<v[i]<<” ”; return (o << endl);

}

cout << v<< endl;

Page 79: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Décalage gauche et droit

Rotations gauche et droites

Apply

#include <valarray>using namespace std;

v.shift(2); cout << v << endl;v.shift(-2); cout << v << endl;

v.cshift(2); cout << v << endl;v.cshift(-2); cout << v << endl;

double array(double i) {return i*i;}v.apply(carre);cout << v << endl;

Page 80: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Retailler

C’est comme un « vector »

#include <valarray>using namespace std;

v.resize(5); cout << v << endl;v.resize(10, 7); cout << v <<endl;

Page 81: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Nouvelles opérations!!!

#include <valarray>using namespace std;

const N =10;valarray}<double> v1(N), v2(N), v3(N);for(int i=0; i<v1.size(); i++)v1[i]=i*1.5;for(int i=0; i<v2.size(); i++)v2[i]=i/3;cout << v1 << endl;cout << v2 << endl;v3 = v1+v2;cout << v3 << endl;

Page 82: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Essayez les opérations arithmétiques

#include <valarray>using namespace std;

v3 = v1+v2;cout << v3 << endl;v3 = v1 – v2;cout << v3 << endl;v3 = v1*v2;cout << v3 << endl;v3 = v1/v2;cout << v3 << endl;

Page 83: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Essayez les opérations logiques

#include <valarray>using namespace std;

v3 = v1 < v2;cout << v3 << endl;v3 = v1 >= v2;cout << v3 << endl;v3 = ~v3;cout << v3 << endl;

Page 84: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray »

Essayez les fonctions mathématiques

#include <valarray>using namespace std;

v3 = sqrt(v1);cout << v3 << endl;v3 = pow(v1,2);cout << v3 << endl;

Page 85: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray » la nouveauté!!!

Indices

Objet de type « slice_array »

Initialisation de la tranche

#include <valarray>using namespace std;

slice(int départ, int taille, int pas);

v1[slice(0,5,2)] // position pairesv1[slice(1,5,2)] // position impaires

v1[slice(0,5,2)] = 0; //position pairev1[slice(1,5,2)] = 1; // positions impaires

Page 86: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

<valarray>

Lib « valarray » la nouveauté!!!

L’opérateur d’affectation est ainsi défini

Affectation!

#include <valarray>using namespace std;

slice_array = valarray;

v1[slice(0,5,2)] = static_cast<valarray>(v1[slice(1,5,2)]);

Page 87: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Les itérateurs

À sens unique

Bidirectionnels

Accès direct

En avant seulement

En avant et en arrière

Idem + indexation

Page 88: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Les itérateurs

Avancer à l’élément suivant

Reculer à l’élément précédent

Accès direct

it++ ou ++it

it– ou –it

it + n ou n + itit - n

it +=nit -= nit[n]

it – jt (distance)i<j

Page 89: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Les itérateurs

Déclarations

iterator

const iterator

reverse_iterator

const reverse_iterator

Page 90: Structures de données IFT-2000 Abder Alikacem La librairie STL du C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Standard Template Library

Les itérateurs

const int N = 10;vector<int> t(N);vector<int>::iterator it; vector<int>::const_iterator cit; vector<int>::reverse_iterator rit; vector<int>::const_reverse_iterator crit;

for(it=t.begin(); it!=t.end(); ++it) *it = rand() % 100; for(cit=t.begin(); cit!=t.end(); ++cit) cout << *cit << ” ”; cout << endl; for(rit=t.rbegin(); rit!=t.rend(); ++rit) *rit *= 2; for(crit=t.rbegin(); crit!=t.rend(); ++crit) cout << *crit << ” ” ; cout << endl;