Dans les premiers chapitres de ce cours, nous avions vu que les pointeurs pouvaient être assimilés à des flèches pointant sur les cases de la mémoire de l'ordinateur. Ce n'est bien sûr qu'une image, mais elle va nous aider dans la suite.
Un conteneur est un objet contenant des éléments. Un peu comme la mémoire contient des variables. Les concepteurs de la STL ont donc eu l'idée de créer des pointeurs spéciaux pour se déplacer dans les conteneurs comme le ferait un pointeur dans la mémoire. Ces pointeurs spéciaux s'appellent des
itérateurs.
Les itérateurs sont en réalité des objets plutôt complexes. Pas juste de simples pointeurs.
L'avantage de cette manière de faire est qu'elle réutilise quelque chose que l'on connaît bien. On peut déplacer l'itérateur en utilisant les opérateurs
++ et
--, comme on pourrait le faire pour un pointeur. Mais l'analogie ne s'arrête pas là, on accède à l'élément pointé (ou itéré
) via l'étoile
*. Bref, ça nous rappelle de vieux souvenirs. Du moins j'espère...
Déclarer un itérateur...
Chaque conteneur possède son propre type d'itérateur, mais la manière de les déclarer est toujours la même. Comme toujours, il faut un type et un nom. Choisir un nom, c'est votre problème
, mais pour le type, je vais vous aider. Il faut mettre le type du conteneur, suivi de l'opérateur
:: et du mot
iterator. Par exemple pour un itérateur sur un
vector d'entiers, on a :
Code : C++ - Itérateur sur un vector d'entiers | #include <vector>
using namespace std;
vector<int> tableau(5,4); //Un tableau de 5 entiers valant 4
vector<int>::iterator it; //Un itérateur sur un vector d'entiers
|
Voici encore quelques exemples:
Code : C++ - D'autres itérateurs | map<string, int>::iterator it1; //Un itérateur sur les tables associatives string-int
deque<char>::iterator it2; //Un itérateur sur une deque de caractères
list<double>::iterator it3; //Un itérateur sur une liste de nombres à virgule
|
Bon. Je crois que vous avez compris.
... et itérer
Il ne nous reste plus qu'à les utiliser. Tous les conteneurs possèdent une méthode
begin() renvoyant un itérateur sur le premier élément contenu. On peut ainsi faire pointer l'itérateur sur le premier élément. On avance alors dans le conteneur en utilisant l'opérateur
++. Il ne nous reste plus qu'à spécifier une condition d'arrêt. On ne veut pas aller en-dehors du conteneur. Pour ce faire, les conteneurs possèdent une méthode
end() renvoyant un itérateur sur la fin du conteneur.
En réalité, end() renvoie un itérateur sur un élément en-dehors du conteneur. Il faut donc itérer jusqu'à end() non compris.
On peut donc parcourir un conteneur en itérant dessus depuis
begin() jusqu'à
end(). Voyons ça avec un exemple :
Code : C++ - Itérer sur une deque 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | #include<deque>
#include <iostream>
using namespace std;
int main()
{
deque<int> d(5,6); //Une deque de 5 éléments valant 6
deque<int>::iterator it; //Un itérateur sur une deque d'entiers
//Et on itère sur la deque
for(it = d.begin(); it!=d.end(); ++it)
{
cout << *it << endl; //On accède à l'élément pointé via l'étoile
}
return 0;
}
|
Les itérateurs ne sont pas optimisés pour l'opérateur de comparaison. On ne devrait donc pas écrire it<d.end() comme on en a l'habitude avec les index de tableau. Utiliser != est plus efficace.
Simple non ? Si vous avez aimé les pointeurs (
), vous allez adorer les itérateurs. Pour les
vector et les
deque, cela peut vous sembler inutile. On peut faire aussi bien avec les crochets
[]. Mais pour les
map et surtout les
list, ce n'est pas vrai, les itérateurs sont le seul moyen que nous avons de les parcourir.
Des méthodes uniquement pour les itérateurs
Même pour les
vector ou
deque, il existe des méthodes qui nécessitent l'emploi d'itérateurs. Il s'agit en particulier des méthodes
insert() et
erase() qui, comme leur nom l'indique, permettent d'ajouter ou supprimer un élément au milieu d'un conteneur. Jusqu'à maintenant, vous ne pouviez qu'ajouter des éléments à la fin d'un conteneur, jamais au milieu. La raison est simple : pour ajouter quelque chose au milieu, il faut indiquer
où l'on souhaite insérer l'élément. Et ça, c'est justement le but d'un itérateur.
Un exemple vaut mieux qu'un long discours.
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 | #include <vector>
#include <string>
#include <iostream>
using namespace std;
int main()
{
vector<string> tab; //Un tableau de mots
tab.push_back("les"); //On ajoute deux mots dans le tableau
tab.push_back("Zeros");
tab.insert(tab.begin(), "Salut"); //On insère le mot "Salut" au début
//Affiche les mots donc la chaine "Salut les Zeros"
for(vector<string>::iterator it=tab.begin(); it!=tab.end(); ++it)
{
cout << *it << " ";
}
tab.erase(tab.begin()); //On supprime le premier mot
//Affiche les mots donc la chaine "les Zeros"
for(vector<string>::iterator it=tab.begin(); it!=tab.end(); ++it)
{
cout << *it << " ";
}
return 0;
}
|
Et c'est la même chose pour tous les types de conteneurs. Si vous avez un itérateur sur un élément, vous pouvez le supprimer via
erase() ou ajouter un élément juste après grâce à
insert().
Souvenez-vous quand même que les vector ne sont pas optimisés pour l'insertion et l'effacement au milieu. Le schéma du chapitre précédent vous aidera à faire un meilleur choix si vous avez vraiment besoin de faire ce genre de modifications sur votre conteneur.
Je vous avais dit que vous alliez adorer ce chapitre ! Et ça ne fait que commencer.
Les différents itérateurs
Terminons quand même avec quelques aspects un petit peu plus techniques. Il existe en réalité 5 sortes d'itérateurs. Lorsque l'on déclare un
vector::iterator ou un
map::iterator, on déclare en réalité un objet d'une de ces cinq catégories. Cela se fait via une redéfinition de type, chose que nous verrons dans la cinquième partie de ce cours.
Parmi les 5 types d'itérateurs, seuls deux sont utilisés pour les conteneurs : les
bidirectional iterators et les
random access iterators. Voyons ce qu'ils nous proposent.
Les bidirectional iterators
Ce sont les plus simples des deux. "Bidirectional iterator" signifie itérateur bidirectionnel, mais cela ne nous avance pas beaucoup...
Ce sont des itérateurs qui permettent d'avancer et de reculer sur le conteneur. Cela veut dire que vous pouvez utiliser aussi bien
++ que
--. L'important étant que l'on ne peut avancer que d'
un seul élément à la fois. Donc pour accéder au 6
ème d'un conteneur, il faut partir de la position
begin() puis appeler cinq fois l'opérateur
++.
Ce sont les itérateurs utilisés pour les
list,
set et
map. On ne peut donc pas utiliser ces itérateurs pour accéder directement au milieu d'un de ces conteneurs.
Les random access iterators
Au vu du nom, vous vous en doutez peut-être, ces itérateurs permettent d'accéder au hasard, ce qui en meilleur français veut dire que l'on peut accéder directement au milieu d'un conteneur.
Techniquement, ces itérateurs proposent en plus de
++ et
-- des opérateurs
+ et
- permettant d'avancer d'un coup de plusieurs éléments.
Par exemple pour accéder au 8
ème élément d'un
vector, on peut utiliser la syntaxe suivante :
Code : C++ | vector<int> tab(100,2); //Un tableau de 100 entiers valant 2
vector<int>::iterator it = tab.begin() + 7; //Un itérateur sur le 8ème élément
|
En plus des
vector, ces itérateurs sont ceux utilisés par les
deque.
Le mécanisme exact des itérateurs est très compliqué, c'est pour cela que je ne vous présente que les éléments qui vous seront réellement nécessaires dans la suite. Savoir que certains itérateurs sont plus limités que d'autres nous sera utile au chapitre suivant puisque certains algorithmes ne sont utilisables qu'avec des random access iterators.
Itérateurs et foncteurs
Durée d'étude :
1
jour
Et puis, il n'y a pas d'opérateur [] pour les listes. On n'a donc pas le choix !
Rien de grave je vous rassure. 
On ne peut rien faire d'autre avec une paire. Elles servent juste à contenir deux objets. 
Mordore
Trouvez une formation
Suggestions
Flux RSS News
Twitter
Facebook
Google+