Les itérateurs : le ciment de la STL
Comprenez les catégories d'itérateurs, des itérateurs d'entrée aux itérateurs contigus. Apprenez l'arithmétique des itérateurs, la convention begin/end et comment les itérateurs connectent les conteneurs aux algorithmes.
L'abstraction des itérateurs
Les itérateurs sont le ciment entre les conteneurs et les algorithmes de la STL. Au lieu d'écrire N algorithmes pour M conteneurs (N*M implémentations), la STL définit une interface commune d'itérateurs. Chaque conteneur fournit des itérateurs et chaque algorithme opère sur des plages d'itérateurs — donnant N+M implémentations qui fonctionnent ensemble.
Un itérateur est un objet qui :
1. Pointe vers un élément dans une séquence
2. Peut être déréférencé (*it) pour accéder à l'élément
3. Peut être incrémenté (++it) pour passer à l'élément suivant
4. Peut être comparé (it != end) pour détecter la fin de la séquence
Différentes catégories d'itérateurs supportent différents ensembles d'opérations, formant une hiérarchie du plus faible au plus puissant.
Catégories d'itérateurs
Les catégories d'itérateurs C++ forment une hiérarchie (chaque niveau inclut les capacités de tous les niveaux inférieurs) :
| Catégorie | Opérations | Conteneurs exemples |
|---|---|---|
| Input | Lecture, parcours avant simple (++, *, ==) | istream_iterator |
| Output | Écriture, parcours avant simple (++, *=) | ostream_iterator, back_inserter |
| Forward | Lecture/écriture, parcours avant multi-passe | forward_list, unordered_set |
| Bidirectional | Forward + recul (--) | list, set, map |
| Random Access | Bidirectional + sauts (+n, -n, [], <) | deque |
| Contiguous (C++17) | Random Access + éléments adjacents en mémoire | vector, array, string |
Les algorithmes déclarent la catégorie minimale qu'ils requièrent. std::sort a besoin d'itérateurs à accès aléatoire, donc il fonctionne avec vector mais pas avec list (qui fournit sa propre fonction membre sort()).
La convention begin/end
Chaque conteneur STL fournit begin() et end() — une plage semi-ouverte [begin, end) où end pointe un élément après le dernier. Les fonctions libres std::begin() et std::end() fonctionnent avec les conteneurs, les tableaux C et tout type qui fournit les membres .begin() et .end().
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>
int main() {
std::vector<int> vec = {5, 3, 1, 4, 2};
// Member functions
auto first = vec.begin(); // points to 5
auto last = vec.end(); // points past 2
// Free functions — preferred for generic code
auto first2 = std::begin(vec);
auto last2 = std::end(vec);
// Works with C-arrays too
int arr[] = {10, 20, 30};
std::sort(std::begin(arr), std::end(arr));
// const iterators — read-only access
auto cit = vec.cbegin(); // const_iterator
// *cit = 99; // ERROR: cannot modify through const_iterator
// Reverse iterators — iterate backward
for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
std::cout << *rit << ' '; // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
}
std::cout << '\n';
}Utilitaires d'itérateurs : next, prev, advance, distance
L'en-tête
#include <iterator>
#include <vector>
#include <list>
#include <iostream>
int main() {
std::vector<int> vec = {10, 20, 30, 40, 50};
// std::next — returns iterator n positions forward (default 1)
auto it = std::next(vec.begin(), 2); // points to 30
std::cout << *it << '\n'; // 30
// std::prev — returns iterator n positions backward
auto it2 = std::prev(vec.end()); // points to 50
std::cout << *it2 << '\n'; // 50
// std::advance — modifies iterator in place (no return)
auto it3 = vec.begin();
std::advance(it3, 3); // now points to 40
std::cout << *it3 << '\n'; // 40
// std::distance — number of increments from first to last
auto d = std::distance(vec.begin(), vec.end()); // 5
std::cout << "Distance: " << d << '\n';
// These work with non-random-access iterators too
std::list<int> lst = {1, 2, 3, 4, 5};
auto lit = std::next(lst.begin(), 2); // O(n) for list, O(1) for vector
std::cout << *lit << '\n'; // 3
auto ld = std::distance(lst.begin(), lst.end()); // O(n) for list
std::cout << "List distance: " << ld << '\n'; // 5
}Itérateurs d'insertion et itérateurs de flux
Les itérateurs d'insertion permettent aux algorithmes d'insérer dans des conteneurs plutôt que d'écraser des éléments existants. Les itérateurs de flux adaptent les flux d'E/S à l'interface d'itérateur.
#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
int main() {
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;
// back_inserter — calls push_back on each assignment
std::copy(src.begin(), src.end(), std::back_inserter(dst));
// dst: {1, 2, 3, 4, 5}
// front_inserter — calls push_front (works with deque, list)
// inserter — calls insert at a given position
// ostream_iterator — write to an output stream
std::copy(dst.begin(), dst.end(),
std::ostream_iterator<int>(std::cout, ", "));
std::cout << '\n'; // 1, 2, 3, 4, 5,
// istream_iterator — read from an input stream
std::istringstream iss("10 20 30 40");
std::vector<int> from_stream(
std::istream_iterator<int>(iss),
std::istream_iterator<int>() // end-of-stream sentinel
);
// from_stream: {10, 20, 30, 40}
}Incrémenter un itérateur au-delà de end() ou décrémenter avant begin() est un comportement indéfini. Il en va de même pour le déréférencement de end() — c'est une sentinelle, pas un élément valide.
Une erreur courante est d'écrire it + 1 sans vérifier si it est déjà à ou près de la fin :
auto it = vec.end();
++it; // UB — au-delà de la fin
*it; // UB — déréférencement de end()Vérifiez toujours la validité des itérateurs avant les opérations. Utilisez std::next et std::prev avec des vérifications de distance, ou utilisez des boucles range-based for qui gèrent les bornes automatiquement.
Lorsque vous écrivez des fonctions génériques qui opèrent sur des séquences :
1. Acceptez des paires d'itérateurs (ou des ranges en C++20) plutôt que des conteneurs spécifiques
2. Utilisez typename ou auto pour le type d'itérateur
3. Utilisez std::distance au lieu de la soustraction (qui nécessite un accès aléatoire)
4. Utilisez std::next/std::prev au lieu de l'arithmétique +/-
5. En C++20, préférez les concepts pour contraindre les exigences d'itérateur :
template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }Cela garantit que votre code fonctionne avec le plus grand nombre de conteneurs.
- Les itérateurs découplent les conteneurs des algorithmes — le principe fondamental de la STL
- Six catégories d'itérateurs existent : input, output, forward, bidirectional, random access, contiguous
- Utilisez les fonctions libres
std::begin()/std::end()pour du code générique fonctionnant avec les conteneurs et les tableaux C std::next,std::prev,std::advance,std::distancefonctionnent avec toutes les catégories d'itérateurs- Les itérateurs d'insertion (
back_inserter,front_inserter,inserter) permettent aux algorithmes d'agrandir les conteneurs - Ne jamais déréférencer
end()ou incrémenter au-delà — les deux sont des comportements indéfinis
Quiz — Testez vos connaissances
(15 XP)1. Quelle catégorie d'itérateur `std::sort` requiert-il ?
2. Que crée `std::back_inserter(vec)` ?
3. Quelle est la complexité temporelle de `std::distance(first, last)` sur une `std::list` ?