Les itérateurs C++ expliqués : begin, end et types d'itérateurs

Ce qu'est réellement un itérateur

Chaque conteneur standard - vector, string, map, set, list - stocke ses éléments différemment en interne. Un vector est un bloc contigu, une map est un arbre équilibré, une list est constituée de nœuds chaînés. Pourtant, on peut tous les parcourir de la même façon. Ce qui rend cela possible, c'est l'itérateur : un petit objet qui « pointe vers » un élément et sait comment avancer jusqu'au suivant.

Voyez un itérateur comme un pointeur généralisé. On en obtient un avec begin(), on lit l'élément vers lequel il pointe avec *, et on le fait avancer avec ++. Les pièces s'assemblent ainsi :

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

int main() {
    vector<int> v = {10, 20, 30};

    vector<int>::iterator it = v.begin();
    cout << *it << "\n";   // 10 - le déréférencement lit l'élément

    ++it;                  // avance vers l'élément suivant
    cout << *it << "\n";   // 20
}

v.begin() renvoie un itérateur vers le premier élément ; *it vous donne cet élément ; ++it passe au suivant. Ce trio - déréférencer, avancer, comparer - constitue tout le modèle mental.

begin(), end() et l'intervalle semi-ouvert

L'autre moitié du tableau est end(). Point crucial : end() ne pointe pas vers le dernier élément - il pointe vers l'emplacement situé juste après le dernier élément. C'est un intervalle « semi-ouvert » délibéré [begin, end) : begin est inclus, end est le signal d'arrêt.

Cette conception rend la boucle standard propre - on parcourt jusqu'à ce que l'itérateur soit égal à end() :

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5};

    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";
}

Notez it != v.end(), et non it < v.end(). La plupart des itérateurs de conteneurs (comme map ou list) ne prennent pas en charge <, seulement == et !=, donc != est le choix portable. Et auto vous évite d'écrire vector<int>::iterator à la main - le compilateur déduit le type.

Le cas du conteneur vide se règle naturellement : lorsqu'un conteneur est vide, begin() == end(), donc le corps de la boucle ne s'exécute jamais. Aucun cas particulier nécessaire.

Ne jamais déréférencer end()

Le bug d'itérateur le plus courant est le déréférencement de end(). Comme il pointe juste après le dernier élément, *v.end() lit de la mémoire qui ne vous appartient pas - un comportement indéfini, c'est-à-dire un plantage ou des données erronées silencieuses, pas une erreur bienveillante :

vector<int> v = {1, 2, 3};
cout << *v.end();   // COMPORTEMENT INDÉFINI - end() n'est pas un élément

Le même piège touche les fonctions de recherche. std::find renvoie end() lorsqu'il ne trouve pas la valeur, vous devez donc vérifier avant de déréférencer :

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {2, 4, 6, 8};

    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        cout << "Found: " << *it << "\n";
    } else {
        cout << "5 is not in the vector\n";   // c'est ceci qui s'exécute
    }
}

Comparez toujours l'itérateur renvoyé à end() avant de le déréférencer. Oublier ce if est l'une des sources de plantages les plus fréquentes dans le code STL des débutants.

const, cbegin et les itérateurs reverse

Les conteneurs fournissent différentes variantes d'itérateurs selon vos besoins :

• begin() / end() - itérateurs normaux en lecture/écriture (*it = ... fonctionne).
• cbegin() / cend() - des const_iterator ; vous pouvez lire à travers eux mais pas modifier l'élément.
• rbegin() / rend() - itérateurs reverse qui parcourent de la fin vers le début ; ++ recule en réalité.

Les itérateurs reverse sont la façon propre de parcourir à l'envers sans calculs d'indices fastidieux :

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

int main() {
    vector<int> v = {1, 2, 3, 4};

    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";   // 4 3 2 1
    }
    cout << "\n";
}

Avec les itérateurs reverse, vous écrivez toujours ++it pour progresser - l'itérateur gère la direction « à l'envers » en interne. Utilisez cbegin()/cend() (ou une référence const au conteneur) lorsqu'une boucle ne doit que lire, afin que le compilateur vous empêche d'écrire par accident.

Les itérateurs de map renvoient des pairs

Tous les itérateurs ne sont pas une mince enveloppe autour d'un pointeur. Un itérateur de std::map parcourt un arbre, et le déréférencer vous donne une std::pair regroupant la clé et la valeur, accessibles via ->first et ->second (tout comme un pointeur, un itérateur prend en charge ->) :

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

int main() {
    map<string, int> ages = {{"Ada", 36}, {"Grace", 85}};

    for (auto it = ages.begin(); it != ages.end(); ++it) {
        cout << it->first << " -> " << it->second << "\n";
    }
}

La boucle for basée sur un intervalle est construite directement sur begin()/end(), donc pour une simple itération en avant, vous y aurez généralement recours. Les itérateurs explicites prouvent leur utilité lorsque vous avez besoin d'un parcours inversé, de la position d'un élément, ou de passer un intervalle à un algorithme.

Le gros piège : l'invalidation des itérateurs

C'est le piège qui finit par mordre tout le monde. Lorsque vous changez la structure d'un conteneur, les itérateurs existants peuvent devenir invalidés - ils pointent vers de la mémoire qui a été libérée ou déplacée. En utiliser un est un comportement indéfini.

Pour un vector, push_back peut réallouer tout le tampon pour l'agrandir, invalidant chaque itérateur en cours. Effacer en parcourant est encore plus notoire - voici un plantage classique :

vector<int> v = {1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0)
        v.erase(it);   // BUG - erase invalide it, puis ++it est un UB
}

La solution est que erase renvoie un itérateur valide vers l'élément suivant celui supprimé. N'avancez que lorsque vous n'avez rien effacé :

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};

    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0)
            it = v.erase(it);   // erase renvoie l'itérateur valide suivant
        else
            ++it;               // n'avance que si rien n'a été supprimé
    }

    for (int x : v) cout << x << " ";   // 1 3 5
    cout << "\n";
}

Remarquez que l'en-tête du for ne contient pas de ++it - c'est le corps qui décide d'avancer ou non. (Dans du vrai code, l'idiome erase-remove ou std::erase_if du C++20 le fait en une seule ligne.) La règle à retenir : toute opération qui ajoute ou supprime des éléments peut invalider les itérateurs, donc ne conservez pas un ancien itérateur à travers un tel changement.

Suite : les algorithmes

Maintenant que vous pouvez décrire un intervalle sous la forme d'une paire begin/end, vous avez débloqué toute la bibliothèque des algorithmes de la STL. Des fonctions comme sort, find, count et accumulate se moquent du conteneur dont vous disposez - elles opèrent sur des intervalles d'itérateurs, si bien que le même appel fonctionne sur un vector, un tableau ou une portion de l'un d'eux. Ensuite, nous mettrons ces itérateurs au travail et laisserons la bibliothèque standard faire les boucles à votre place.