Et si je vous disais que, maintenant que vous connaissez tout sur
std::map et surtout sur les itérateurs des conteneurs STL, apprendre les autres ne sera qu'une formalité ?
Les conteneurs STL sont séparés en trois parties :
- Les autres conteneurs séquentiels qui ont une interface similaire à std::vector, mais représentent néanmoins des concepts différents et ne sont pas prévus pour le même usage. Il s'agit de std::deque et std::list.
- Les adaptateurs de conteneurs réduisant les possibilités d'un std::vector à quelques fonctions, vous pourriez très bien faire ces classes vous même, héritant de std::vector par exemple.
Il s'agit de std::stack, std::queue et std::priority_queue.
- Et bien entendu les conteneurs associatifs ! Vous les connaissez bien maintenant.
Sachez qu'il existe encore un conteneur associatif dont je ne parlerai pas : std::bitset, il permet de stocker des bits sur juste l'espace suffisant : 8 bits sur un octet.
Et bien entendu, vous devrez inclure les headers pour chaque classe utilisée.
Code : C++ | #include <stack>
#include <deque>
#include <queue> // Qui contiendra aussi priority_queue :)
//etc.
|
Les adaptateurs de conteneurs de la STL
Ces classes sont faites pour n'être utilisées qu'avec quelques fonctions pour une utilisation bien précice :
std::stack (ou pile pour les anglophobes )
Cette classe est utilisée quand le tableau est réduit à une pile, par exemple une pile de feuilles (qui à la fin des examens s'est dispersée dans toute ta chambre
).
Que peut-on faire avec une pile (à part la disperser...) ?
- Ajouter des éléments à son sommet. La fonction à utiliser pour cette action sera ... stack::push, elle se comporte exactement comme push_back...
- Accéder à son élément à son sommet. La fonction sera ... stack::top, elle se comporte comme back ou front. Mais ici on n'a pas l'embarras du choix car le seul élément auquel on peut accéder est l'élément au sommet (at the top).
- Supprimer l'élément au sommet, ce qui permettera d'accéder aux éléments en dessous. La fonction sera...stack::pop... Sans commentaires, cette fonction ne prend aucun paramètre et ne renvoie rien, elle ne fait juste qu'enlever l'élément at the top. Et si la pile est vide ben.. Elle reste vide...
Cette classe a bien entendu les fonctions habituelles comme
size ou
empty.
Petite subtilité, cette classe a quand même un paramètre template caché !
C'est la classe qui devra être utilisée pour contenir les éléments, un des trois conteneurs séquentiels. Par défaut, ce paramètre est
std::deque<T> (où T est le type des éléments contenus).
std::queue (prononcez Quiouu) (ou file pour les francophones n'aimant pas dire "Je fais la queue" )
Dans le même état d'esprit de simplification, voici la classe représentant une file :
std::queue.
C'est comme une pile sauf qu'on ajoute les éléments à la fin de la file histoire que le premier arrivé soit le premier servi !
Ben oui, les éléments qui arrivent plus tard, ils n'ont qu'à faire la queue !
Ainsi, la fonction
stack::top est remplacée ici par
queue::front (Premier élément de la file, celui-ci qui va être traité) et
queue::back (Dernier élément de la file, il attendra son tour !). La fonction
queue::push ajoute un élément à la fin de la file et
queue::pop supprime le premier élément (après lui avoir donné son paquet de timbres bien entendu ! ).
Vous pouvez aussi choisir le type de conteneur utilisé bien que le paramètre par défaut est le plus efficace.
std::priority_queue (prononcez Pwraïowrity quiouu)
Cette classe est un peu plus développée que les deux autres que je viens de
présenter platement décrire.
Vous pouvez ajouter des éléments avec
priority_queue::push mais celui-ci ne vas pas toujours se placer au début comme une pile ou à la fin comme une file mais
à sa place, de telle sorte que les plus importants éléments soient au début de la liste. Ainsi cela vous permet de toujours traiter en premier l'élément avec la priorité la plus grande
(avec
priority_queue::top).
Mais, comment cette classe sait quel élément a
de l'importance ?
Il utilise la même technique que
std::map pour trier ses éléments.
Alors, vous vous en souvenez ? Il utilise une classe foncteur de
Comparaison qui permettra de savoir quel est l'élément le plus important entre deux.
Cette classe foncteur était écrite dans le troisième paramètre template de
std::map, et ben pour
priority_queue, c'est aussi le 3ème paramètre template, le deuxième étant, rappelez vous, la classe utilisée pour contenir les éléments.
Je trouve que cette classe mérite un petit exemple, sous forme d'histoire (J'ai été inspiré là
).
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12 | struct PvMin
{
bool operator()(const Personnage & p1, const Personnage & p2) const
{
return p1.vie() > p2.vie();
}
};
#include <queue>
int main()
{
cout << "Il était une fois un petit village de Personnage (symbolisé ici par un vector étant une priority_queue)" << endl;
priority_queue<Personnage, vector<Personnage>, PvMin> village;
|
Voilà comment utiliser le paramètre template. Vous voulez vraiment la suite du code ? Ma petite histoire
?
Secret (cliquez pour afficher)Code : C++ - La petite histoire13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70 | cout << "Il contient un certain nombre d'habitants" << endl;
village.push(Personnage("Bob")); //Bob, toujours en pleine santé
village.push(Personnage("Viellard du coin",10)); // Le viellard du coin
village.push(Personnage("Marie",75));
village.push(Personnage("Sophie",75));//Les deux jumelles, aussi en forme l'une que l'autre
village.push(Personnage("Gaston",60));//Le brave gars :)
village.push(Personnage("Alphonse",90));//Le sportif :)
cout << "Mais malheureusement les conditions de vie dans ce village sont dures : chaque jour le personnage avec le moins de santé s'exile tellement dures elles sont, observez par vous même :" << endl;
int i = 1;
while(i<=3)
{
cout << "---" << endl;
cout << "Jour " << i << endl;
cout << "Aujourd'hui, on entend quelqu'un se présenter :" << endl;
village.top().sePresenter();
cout << "Il s'avère que cette personne a voulu quitter le village ..." << endl;
village.pop();
cout << "Il reste " << village.size() << " habitants" << endl;
i++;
}
cout << "Un nouvel habitant arrive dans ce village : " << endl;
Personnage nouveau("Alfred",80);
cout << "Poli, il se présente : " << endl;
nouveau.sePresenter();
village.push(nouveau);
while(! village.empty())
{
cout << "---" << endl;
cout << "Jour " << i << endl;
cout << "Aujourd'hui, on entend quelqu'un se présenter :" << endl;
village.top().sePresenter();
cout << "Il s'avère que cette personne a voulu quitter le village ..." << endl;
village.pop();
cout << "Il reste " << village.size() << " habitants" << endl;
i++;
}
cout << "Le village est maintenant abandonné.. Il devient une ville fantôme.." << endl;
return 0;
}
|
Exécutez ce code après avoir rajouté une fonction
int vie() aux Personnages, la console vous racontera une petite histoire.
Le test de comparaison d'importance ne se fait que lors de
l'ajout d'un élément dans la
priority_queue. Si un élément dans la file acquiert plus (ou moins) d'importance, il ne sera plus à sa place et la file ne fera plus ce qu'elle devra ! Par exemple, dans l'algorithme de Dijkstra, un élément dans la liste ouverte peut voir son poids descendre et donc sa place devrait être changée dans la file. Si de tels cas apparaissent, il faut utiliser uen autre classe pour faire la file de priorité.
Exemple de problème :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | struct Comp
{
bool operator()(int * un, int * deux)
{
cout << "Comparaison" << endl;
return *un < *deux;
}
};
int main()
{
int a(2), b(7);
priority_queue<int*, vector<int*>, Comp> f;
f.push(&a);
cout << *f.top() << endl; //2 ... Normal
f.push(&b);
cout << *f.top() << endl; //7 ... Normal car l'élément a une plus grande importance
b = 0;
cout << *f.top() << endl; //0 ... Pas normal, cela devrait être 2
return 0;
}
|
Cela devrait être l'adresse de a en premier dans la file. Mais quand on met la valeur de b à zéro, le conteneur ne se doute pas qu'une importance a changé dans ses éléments.
Pour éviter ce problème, il faut se dire que quand on ajoute un élément, le conteneur fait une comparaison avec les éléments existants pour placer le nouvel arrivant à sa place. Et c'est le seul moment où il fait des comparaisons.
Si on a besoin de faire changer les importances des éléments dans la file, il faut faire sa propre file de priorité (implémenté généralement sous forme de tas).
Les autres conteneurs séquentiels de la STL
std::deque (Double Ended Queue si vous voulez tout savoir ...)
std::deque est une classe qui s'utilise de la même façon que vector ! Les fonctions que vous connaissez pour vector pourront aussi être utilisées ici.
Néanmoins
std::deque possède deux différences :
- Un std::vector est optimisé pour que les nouveaux éléments soient ajoutés à la fin, c'est pourquoi il possède une fonction push_back et pop_back. std::deque
est lui par contre optimisé pour que les nouveaux éléments soient ajoutés à la fin .. ou au début ! Il possède donc les fonctions push_front et pop_front en plus que std::vector.
- Les éléments de std::vector sont stockés comme pour un tableau en c, à des places continues de la mémoire alors qu'avec std::deque, pas nécessairement. Cela n'a pas d'importance tant qu'on ne doit pas faire de conversions du style std::vector => tableau C-like.
D'ailleurs, je vous informe que les itérateurs de
std::vector et
std::deque sont arithmétiques (
RandomAccess iterator) !
Euh mais c'est quoi un itérateur arithmétique ?
Cela veut simplement dire que vous pouvez écrire ceci :
Code : C++ | vector<int> v(10,2);
vector<int>::iterator it = v.begin();
it = it + 5;
it -= 5;
|
Utiliser des opérateurs arithmétiques pour se déplacer plus vite dans le tableau.
Ceux des tableaux associatifs par exemple avaient les opérateurs !=, ==, ++ (etc.) surchargés. Ceux-ci en a plus, c'est tout. Si vous voulez savoir quels itérateurs possèdent quelles surcharges d'opérateur, jetez un coup d'oeil à
cette page.
Vous pouvez même voir que ces
RandomAccess iterator ont par exemple les opérateurs < et > surchargés.
Les itérateurs de
std::list et des tableaux associatifs étaient appelés
Bidirectional iterator car avec l'un de ces itérateurs on peut accéder à l'itérateur
suivant et
précédent uniquement (avec les opérateurs ++ et --).
La fonction std::advance(itérateur, nb) peut-être utilisée pour avancer un itérateur de la valeur nb. Si l'itérateur est arithmétique, C++ utilisera l'opérateur += ou -= sinon il fera une boucle de ++ ou --.
Bref, utilisez
std::deque si vous avez besoin d'insérer des éléments autant au début qu'à la fin du tableau.
Et si vous avez besoin d'insérer des éléments au milieu ... Voici le dernier conteneur de la STL :
std::list
Un élément stocké dans une
std::list prendra plus de place en mémoire qu'un
std::vector mais vous fournira des performances bien meilleures si vous avez besoin d'effectuer beaucoup de déplacements à l'intérieur de la liste : élimination, déplacement de bloc d'une liste à l'autre ou dans la même, ajout d'éléments après un certain autre etc.
Les fonctions principales de
std::list sont
list::insert et
list::erase que vous connaissez bien.
Cependant
list::insert ne s'utilise pas exactement de la même manière, voici ses prototypes :
Code : C++ | itérateur insert(itérateur position, const Valeur & x);
void insert(itérateur position, size_t nombre, const Valeur & x);
void insert(itérateur position, itérateur debut, itérateur fin);
|
est un itérateur qui indique
avant quel élément la valeur doit être insérée.
Pour la deuxième surcharge, cela permet d'indiquer combien d'éléments identiques ajouter et pour la troisième cela permet d'ajouter les éléments avant
position DE
debut À
fin -non compris-, de la même manière qu'on avait fait avec
std::map :
Code : C++ | //si groupe1 et groupe deux sont des std::map
groupe1.insert(groupe2.begin(), groupe2.end()); //On ajoute le groupe 2 au groupe 1
//si groupe1 et groupe2 sont des std::list
groupe1.insert(groupe1.end(), groupe2.begin(), groupe2.end()); //On ajoute le groupe 2 à la fin du groupe 1
|
Un peu de généricité
Vous savez quoi ?
std::vector (et
std::deque bien sûr) possède
exactement la même fonction ! Mais je vous rappelle que
std::vector est optimisé pour des insertions à la fin seulement (et
std::deque pour des insertions à la fin ou au début).
Une utilisation pratique est la fusion de deux tableaux comme montré ci-dessus ou encore cette utilisation ci-dessous que je trouve très pratique :
Code : C++ | int tabC[5] = {5, 2, -99, 12, 0xFF9900}; //Un tableau C-like initialisé avec une liste d'initialisation !
vector<int> tab;
tab.insert(tab.end(), tabC, tabC + 5); //Waw ! Le tableau C-like est considéré comme un itérateur ! On insère avant end() DE tabC à tabC + 5 -non compris- ! Que c'est pratique !
|
Et encore pour avoir un code plus clair. Il existe un constructeur surchargé pour les itérateurs qui prend une paire d'itérateur pour savoir avec quoi le conteneur doit être rempli. Le code ci-dessus peut s'écrire en deux lignes :
Code : C++ | int tabC[5] = {5, 2, -99, 12, 0xFF9900}; //Un tableau C-like initialisé avec une liste d'initialisation !
vector<int> tab(tabC, tabC + 5); //Initialisé avec les itérateurs !
|
Cette surcharge qui permet un raccourci de la fonction
insert est présente dans
tous les conteneurs (même les associatifs !)
Mais, si je voulais utiliser le constructeur qui prenait comme paramètre un foncteur ? Et aussi celui-là ?
Il existe encore un constructeur qui mixe les deux. D'abord les itérateurs, et puis les foncteurs (après tous, vous les avez appris dans cet ordre la non ?) :
Code : C++ | map<Coordonnees, Personnage*> terrain(m1.begin(), m1.end(), monFoncteur);
|
Quelques fonctions pratiques que propose std::list
list::assign et list::resize
Ce sont
exactement les mêmes fonctions que celles de
std::vector. Sachez néanmoins que
assign peut être utilisée avec des itérateurs (maintenant que vous les connaissez) :
Code : C++ | list<string> maListe;
list<string> maListe2;
maListe.assign(5,"Blaaaaaaaaa"); //La première liste contient 5 Blaaaaaaaaa maintenant.
maListe2.assign(maListe.begin(), maListe.end()); //Une copie de maListe
|
list::splice
Cette fonction est une manière plus rapide de déplacer-effacer des éléments à traver une même liste ou plusieurs. Vous pouvez l'utiliser de 3 manières différentes, voyez par vous-même (exemple platement pris de
mon site de référence) :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | list<int> liste1;
list<int> liste2;
for(int i = 1;i<5;i++)
liste1.push_back(i); //liste1 : 1,2,3,4
for(int i = 20;i<25;i++)
liste2.push_back(i); // liste2 : 20,21,22,23,24
liste<int>::iterator it = liste1.begin(); //it pointe vers 1
it++; //it pointe vers 2
liste1.splice(it, liste2); // La liste 2 sera placée toute entière dans la liste1 juste avant l'élément pointé par it;
//liste1 : 1,20,21,22,23,24,2,3,4
//it pointe toujours vers 2
cout << liste2.empty(); // true, la liste a été été vidée
liste2.splice(liste2.begin(), liste1, it);//Place avant liste2.begin() l'élément de liste1 pointé par it
//liste1 : 1,20,21,22,23,24,3,4
//liste2 : 2
it = liste1.begin(); // it pointe vers 1
advance(it,5); //it pointe sur 24
liste1.splice(liste1.begin(), liste1, it, liste1.end()); //Prendre les éléments de liste1 DE it À liste1.end()-non compris- et les placer avant liste1.begin()
//liste1 : 24,3,4,1,20,21,22,23
it = liste1.begin();//Pointe 24
advance(it,1);//pointe 3
liste<int>::iterator it2 = it; // Pointe 3
advance(it,3); //pointe 20
liste2.splice(liste2.end(), liste1, it, it2); //prendre les éléments de liste1 DE it À it2-non compris- et les placer avant liste2.end()
//liste1 : 24,20,21,22,23
//liste2 : 2,3,4,1
|
list::remove
Permet de supprimer tous les éléments d'une liste ayant une certaine valeur. Exemple :
liste.remove(5); supprimera tous les éléments égaux à 5 dans la liste. Cette fonction utilise l'
operator==.
list::remove_if
Permet de supprimer tous les éléments d'une liste satisfaisant une certaine condition. Le paramètre à indiquer est un
prédicat prenant comme paramètre un élément de la liste.
Par exemple pour enlever tous les Personnages avec une vie de plus de 50 d'une liste de Personnage :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12 | bool vie_plus_grande_que_50(const Personnage & p)
{
return p.vie() > 50;
}
class Classe_vie_plus_grande_que_50
{
public:
bool operator()(const Personnage & p)
{
return p.vie() > 50;
}
};
|
| list<Personnage> liste;
//Remplissage avec push_back, push_front, insert, assign etc.
liste.remove_if(vie_plus_grande_que_50); //en utilisant une fonction comme prédicat :
Classe_vie_plus_grand_que_50 leFoncteur; //On crée un foncteur, je dirais même un prédicat
liste.remove_if(leFoncteur); //en utilisant un objet d'une classe comme prédicat, la fonction appellera son operator()
|
L'utilisation de la classe permet beaucoup de choses ! Comme par exemple ceci :
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12 | class Classe_vie_plus_grande
{
private :
int _val;
public:
Classe_vie_plus_grande(int val) : _val(val)
{}
bool operator()(const Personnage & p)
{
return p.vie() > _val;
}
};
|
| Classe_vie_plus_grande monFoncteur(50);
liste.remove_if(monFoncteur);
|
Ou en une ligne :
Code : C++ | liste.remove_if(Classe_vie_plus_grande(50));
|
list::unique
Permet de supprimer tous les doublons consécutifs d'une liste.
C'est à dire qu'après avoir exécuté cette fonction, la liste ne contiendra plus deux éléments égaux l'un à côté de l'autre.
- Si vous n'indiquez aucun paramètre, l'operator== sera utilisé.
- Si vous voulez comparer des éléments selon un autre critère, mettez en paramètre un prédicat permettant de comparer les éléments.
list::reverse
Cette fonction renverse l'ordre des éléments, les premiers seront les derniers et les derniers seront les premiers ! Si ça peut vous être utile un jour...
list::sort !
Cette fonction trie les éléments d'un tableau !
- Soit elle ne prend aucun paramètre, l'operator< est alors utilisé.
- Soit un paramètre Prédicat de Comparaison que vous connaissez bien (Ben oui, vous vous rappelez quand même de notre foncteur Comparaison non ? ).
Un petit exemple même si vous avez déjà tout compris :
Code : C++ | struct Tri_par_vie
{
bool operator()(const Personnage & p1, const Personnage & p2)
{
return p1.vie() < p2.vie();
}
};
|
| liste.sort( Tri_par_vie() );//Les parenthèses permettent de créer un foncteur avec le constructeur par défaut
|
Une petite astuce de types !
Tous les conteneurs mettent à disposition le type des éléments qu'ils contiennent. Par exemple, un
vector<int> contient des
int et un
vecteur<Personnage*> des
Personnage*
Les conteneurs associatifs mettent également à disposition le type de la clef utilisé. Rappelez-vosu que les
std::map contiennent des paires !
Voici comment obtenir ces types : avec les mot-clefs
value_type et
key_type.
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14 | vector<int> v;
vector<int>::value_type elemVec; //type int
v.push_back(elemVec);
map<string, Personnage*> m;
map<string, Personnage*>::value_type elemMap; //type pair<string, Personnage*>
map<string, Personnage*>::key_type nom = "Bob"; //type string
elemMap.first = nom;
elemMap.second = new Personnage;
m.insert(elemMap);
|
Ce code peut paraître un peu idiot, mais en modifiant comme ceci, ce serait déjà mieux !
Code : C++ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | typedef myVec vector<int>;
typedef myMap map<string, Personnage*>;
myVec v;
myVec::value_type elemVec; //type int
v.push_back(elemVec);
myMap m;
myMap::value_type elemMap; //type pair<string, Personnage*>
mmyMap::key_type nom = "Bob"; //type string
elemMap.first = nom;
elemMap.second = new Personnage;
m.insert(elemMap);
|
Dans certains cas, il suffira juste de changer les
typedef.
Utilisation dans une classe template
Dans le cas d'une classe template, cela peut devenir nécessaire ! Imaginez une classe template qui manipule une
map et un
vector. Que choisirions nous comme paramètre template ?
Code : C++ | MyMap m;
MyVec v;
Manipule<???> manip(m, v);
|
Dans cet exemple, nous pourrions mettre
Manipule<string, Personnage*, int> et donc dans la définition :
Code : C++ | template <typename Clef, typename ValeurM, typename ValeurV>
class Manipule
{
Clef c; ValeurM m; ValeurV v;
Manipule( std::map<Clef, ValeurM>&, std::vector<ValeurV> >);
}
|
Mais ceci n'est pas toujours correct car par exemple std::map peut avoir un paramètre template en plus, celui de Comparaison. Donc il faudrait modifier les paramètres template et cela deviendrait bien compliqué. Ce qu'on aimerait c'est :
Code : C++ | Manipule<MyMap, MyVec> m;
|
Mais dans la classe template, on aimerait par exemple avoir la clef de la
map ou le type des éléments du
vector. Et donc c'est là qu'intervient l'astuce.
Code : C++ | template <typename LaMap, typename LeVec>
class Manipule
{
typedef typename LaMap::key_type Clef;
typedef typename LaMap::value_type ValeurM;
typedef typename LeVec::value_type ValeurV;
Clef c; ValeurM m; ValeurV v;
Manipule( std::map<Clef, ValeurM>&, std::vector<ValeurV> );
}
|
Observez l'obligation d'utiliser le mot clef typename pour indiquer au compilateur que nous définissons un type ! En effet, LaMap::key_type par exemple pourrait être une variable de type static ou une fonction de la classe !
Et dans notre classe, nous pourrions créer un itérateur par exemple !
Et les itérateurs pointent toujours vers... un élément contenu dans le conteneur ! Donc ...
value_type !
Exemple dans la classe
Manipule :
Code : C++ | typedef typename LaMap::iterator IteratorM;
typedef typename LeVec::iterator IteratorV;
//On sait que les IteratorM pointeront vers ValeurM !
|
Les Conteneurs de la STL
Durée d'étude :
2
heures,
30
minutes
yoch
), car cela demande d'actualiser la valeur size pour chaque modification de la liste, et donc va flinguer les perfs d'autres fonctions comme insert(), assign() ou splice() qui passeront de O(1) à O(n) dans certains cas (passage de sous-liste par itérateurs, à moins qu'il existe un moyen de contrer cela, perso je ne vois pas)... [à confirmer]
Trouvez une formation
Suggestions
Twitter
Facebook
Google+