Les itérateurs

Les trois méthodes de parcours

Méthode	Type de l’`Item`	Effet sur la collection
`iter()`	`&T`	Empruntée en lecture, réutilisable ensuite
`iter_mut()`	`&mut T`	Empruntée en écriture, réutilisable ensuite
`into_iter()`	`T`	Consommée, si le receveur est possédé

La nuance qui échappe le plus souvent : into_iter() est polymorphe sur son receveur.

let mut v: Vec<String> = vec!["a".into(), "b".into()];

v.into_iter()           // Item = String     (v est consommé)
(&v).into_iter()        // Item = &String    (équivaut à v.iter())
(&mut v).into_iter()    // Item = &mut String (équivaut à v.iter_mut())

Il existe en effet trois implémentations distinctes de IntoIterator : une pour Vec<T>, une pour &Vec<T> et une pour &mut Vec<T>. C’est ce qui fait fonctionner for x in &v.

Les trois traits

Trait	Méthode clé	Signification
`Iterator`	`fn next(&mut self) -> Option<Self::Item>`	« je suis un itérateur »
`IntoIterator`	`fn into_iter(self) -> Self::IntoIter`	« je peux devenir un itérateur »
`FromIterator`	`fn from_iter(iter) -> Self`	« je peux être construit depuis un itérateur », ce qu’appelle `collect()`

Iterator n’a qu’une seule méthode requise : next(). La soixantaine d’autres (map, filter, fold…) sont des méthodes par défaut définies à partir d’elle. C’est pourquoi écrire un itérateur personnalisé coûte quelques lignes et donne accès à tout l’écosystème.

Note

Il n’existe pas de trait Iter. La méthode iter() est une méthode inhérente à chaque collection, par pure convention. Sur Vec<T>, elle provient même de la slice [T] via Deref : Vec n’a pas de iter() en propre — voir Le mécanisme Deref.

Ce que fait réellement une boucle `for`

for x in expression { ... } est réécrit par le compilateur en :

let mut it = IntoIterator::into_iter(expression);
while let Some(x) = it.next() {
    // ...
}

Une boucle for appelle donc toujours into_iter(). Ce qui varie, c’est le type de l’expression :

for s in v          {}      // s: String     — v est déplacé, inutilisable ensuite
for s in &v         {}      // s: &String    — v reste disponible
for s in &mut v     {}      // s: &mut String
for s in v.iter()   {}      // s: &String    — identique à &v

Si v.iter() fonctionne dans un for alors que c’est déjà un itérateur, c’est grâce à une implémentation générale :

impl<I: Iterator> IntoIterator for I {
    type Item = I::Item;
    fn into_iter(self) -> I { self }        // Identité
}

Tout Iterator est donc trivialement un IntoIterator.

Tip

Convention d’écriture : for x in &v dans une boucle simple, plus court et plus lisible ; v.iter().filter(...).map(...) dans une chaîne d’adaptateurs, où un Iterator est indispensable.

Le cas des tableaux

Historiquement, [T; N] n’implémentait pas IntoIterator par valeur : tableau.into_iter() passait par auto-référencement vers &[T; N] et produisait des &T. Le défaut a été corrigé, mais avec une compensation pour préserver la compatibilité.

Édition	`tableau.into_iter()`
2015 / 2018	`Item = &T`, par résolution via auto-référencement
2021 / 2024	`Item = T`

En édition 2021 et suivantes, il n’y a plus de surprise. Du code appelant IntoIterator::into_iter(tableau) en syntaxe de fonction est un contournement de l’époque 2018, qui peut être simplifié.

Note

Une slice [T] n’a pas de taille connue et ne peut donc pas être consommée par valeur : seules &[T] et &mut [T] implémentent IntoIterator. Pour extraire les valeurs d’un Vec sans le détruire, il y a drain().

Tableau par collection

Collection	`iter()`	`iter_mut()`	`into_iter()`
`Vec<T>` / `[T]`	`&T`	`&mut T`	`T`
`HashMap<K, V>`	`(&K, &V)`	`(&K, &mut V)`	`(K, V)`
`HashSet<T>`	`&T`	— (casserait le hachage)	`T`
`BTreeMap<K, V>`	`(&K, &V)`, trié	`(&K, &mut V)`	`(K, V)`
`Option<T>`	`&T`	`&mut T`	`T`
`Result<T, E>`	`&T`	`&mut T`	`T`
`String`	— (`chars()` ou `bytes()`)	—	—

Variantes utiles sur les tables associatives :

map.keys()              // &K
map.values()            // &V
map.values_mut()        // &mut V
map.into_keys()         // K
map.into_values()       // V
map.drain()             // (K, V), vide la table mais conserve l'allocation

Que Option et Result se comportent comme des itérateurs de zéro ou un élément n’est pas une curiosité : c’est ce qui permet à flatten() de fonctionner sur un Iterator<Item = Option<T>>, comme décrit dans Le type Option.

La paresse

Les adaptateurs ne font rien. Ils construisent une structure qui décrit le travail à accomplir, et rien ne s’exécute avant l’intervention d’un consommateur.

v.iter().map(|x| println!("{x}"));       // N'affiche rien

Iterator étant annoté #[must_use], le compilateur émet ici un avertissement.

Le corollaire est positif : enchaîner six adaptateurs ne provoque pas six passes sur les données. Tout est fusionné en une seule passe au moment de la consommation, et l’optimiseur produit généralement une boucle équivalente à sa version impérative écrite à la main.

Adaptateurs et consommateurs

Adaptateurs — ils retournent un `Iterator`

map / filter / filter_map / flat_map / flatten
take / skip / take_while / skip_while / map_while / step_by
chain / zip / enumerate / rev / cycle
peekable / scan / inspect / by_ref
cloned / copied            (Iterator<Item = &T> -> Iterator<Item = T>)

Consommateurs — ils terminent la chaîne

collect / for_each / fold / try_fold / reduce
sum / product / count / last / nth
min / max / min_by_key / max_by_key / min_by / max_by
any / all / find / find_map / position
partition / unzip

Quelques nuances

filter_map est préférable à map(...).filter(...).map(...). La forme filter_map(|x| x.parse().ok()) est l’idiome pour « transformer en écartant les échecs ».
fold et reduce diffèrent par leur point de départ : fold reçoit un accumulateur initial et peut changer de type, reduce part du premier élément et retourne un Option<T>.
zip s’arrête au plus court, silencieusement. C’est une source de bogues discrets.
rev() exige un DoubleEndedIterator : disponible sur les slices, Vec et BTreeMap, mais pas sur HashMap ni derrière un adaptateur qui perd cette propriété.
by_ref() emprunte l’itérateur au lieu de le consommer, ce qui permet de le reprendre ensuite :

let mut it = donnees.iter();
let entete: Vec<_> = it.by_ref().take(3).collect();
let corps: Vec<_> = it.collect();       // it est toujours utilisable

Entre cloned() et copied(), préférer copied() dès que T: Copy : c’est plus explicite et cela documente l’absence de coût.

`collect()`

collect() est générique sur son type de retour via FromIterator. La cible doit donc toujours être annotée :

let v: Vec<_> = it.collect();
let v = it.collect::<Vec<_>>();             // Syntaxe turbofish
let m: HashMap<K, V> = paires.collect();    // Depuis un Iterator<Item = (K, V)>
let s: String = caracteres.collect();
let ensemble: HashSet<_> = it.collect();

Deux formes méritent une attention particulière :

// Tout ou rien : la première erreur court-circuite la chaîne
let nombres: Result<Vec<u32>, _> = chaines.iter().map(|s| s.parse()).collect();

// Équivalent avec Option
let nombres: Option<Vec<u32>> = chaines.iter().map(|s| s.parse().ok()).collect();

Cela fonctionne parce que Result<V, E> implémente FromIterator<Result<T, E>> dès lors que V: FromIterator<T>.

Warning

collect() alloue. Il faut enchaîner tous les adaptateurs avant de collecter, et ne jamais insérer un collect() intermédiaire par simple confort de lecture. Si un point de lisibilité est nécessaire, mieux vaut extraire une fonction qui retourne un impl Iterator.

Retourner un itérateur

Trois possibilités, par ordre de préférence :

// 1. impl Trait : aucun coût, le type concret reste opaque
fn enfants(&self, id: NoeudId) -> impl Iterator<Item = &Noeud> + '_ {
    self.noeuds.iter().filter(move |n| n.parent == Some(id))
}

// 2. Box<dyn Iterator> : quand les branches retournent des types différents
fn parcourir(&self, mode: Mode) -> Box<dyn Iterator<Item = &Noeud> + '_> {
    match mode {
        Mode::Plat => Box::new(self.noeuds.iter()),
        Mode::Trie => Box::new(self.noeuds_tries()),
    }
}

// 3. Type concret exposé : verbeux, et couple l'API à l'implémentation
fn enfants_concret(&self) -> std::slice::Iter<'_, Noeud> {
    self.noeuds.iter()
}

L’annotation + '_, ou une durée de vie nommée, est obligatoire dès que l’itérateur emprunte self.

Info

En édition 2024, les règles de capture des durées de vie dans un impl Trait ont été assouplies : impl Iterator<Item = &Noeud> capture désormais par défaut les durées de vie en portée, ce qui rend le + '_ souvent superflu.

Écrire son propre itérateur

Une seule méthode à implémenter :

struct Ancetres<'a> {
    arbre: &'a Arbre,
    courant: Option<NoeudId>,
}

impl<'a> Iterator for Ancetres<'a> {
    type Item = &'a Noeud;

    fn next(&mut self) -> Option<Self::Item> {
        let id = self.courant?;
        let noeud = self.arbre.get(id)?;
        self.courant = noeud.parent;
        Some(noeud)
    }
}

map, filter, take_while ou collect sont alors disponibles sans effort supplémentaire.

Tip

Avant d’en arriver là, il faut vérifier que le module std::iter ne fait pas déjà le travail :

use std::iter;

iter::successors(Some(depart), |n| n.parent)    // Exactement le cas ci-dessus
iter::from_fn(|| { /* ... */ })                 // Une closure devient un itérateur
iter::once(x)
iter::empty()
iter::repeat(x)
iter::repeat_with(f)

successors couvre la quasi-totalité des remontées de chaîne : parents, liens, pointeurs vers l’élément suivant.

Implémenter `IntoIterator` pour son propre type

Le pattern canonique consiste à fournir les trois implémentations :

impl IntoIterator for Arbre             { type Item = Noeud;        /* ... */ }
impl<'a> IntoIterator for &'a Arbre     { type Item = &'a Noeud;    /* ... */ }
impl<'a> IntoIterator for &'a mut Arbre { type Item = &'a mut Noeud; /* ... */ }

Auxquelles s’ajoutent, par convention, les méthodes inhérentes iter() et iter_mut() qui délèguent aux deux dernières. Le coût est de quelques lignes ; en échange, le type fonctionne dans une boucle for et dans toutes les chaînes d’adaptateurs.

Pièges courants

Mutation pendant l’itération

Le grand classique : une collection ne peut pas être modifiée pendant son parcours.

// Ne compile pas : v est emprunté immuablement par iter(), et muté par push
for x in v.iter() {
    if *x > 10 {
        v.push(0);
    }
}

Les solutions, par ordre de préférence :

// 1. La méthode dédiée existe souvent
v.retain(|x| *x <= 10);                     // Suppression conditionnelle
v.iter_mut().for_each(|x| *x *= 2);         // Mutation en place

// 2. Collecter les décisions, puis les appliquer
let a_ajouter: Vec<_> = v.iter().filter(|x| **x > 10).map(|_| 0).collect();
v.extend(a_ajouter);

// 3. Boucle par index, en dernier recours
for i in 0..v.len() { /* ... */ }

Cloner alors que l’on possède la collection

// Clone chaque élément inutilement
let noms: Vec<String> = utilisateurs.iter().map(|u| u.nom.clone()).collect();

// Si utilisateurs n'est plus nécessaire ensuite
let noms: Vec<String> = utilisateurs.into_iter().map(|u| u.nom).collect();

into_iter() est l’outil anti-clone. Dès qu’un .clone() apparaît dans un map, il faut se demander si l’original est encore utile.

Collection déplacée par une boucle `for`

for x in v {}
println!("{v:?}");      // Erreur : v a été consommé

Symptôme classique de l’oubli du &. Le message du compilateur (borrow of moved value) désigne le bon endroit, mais la cause — la réécriture en into_iter() — n’est pas évidente la première fois.

`collect()` intermédiaire inutile

// Deux allocations
let a: Vec<_> = it.filter(f).collect();
let b: Vec<_> = a.iter().map(g).collect();

// Une seule
let b: Vec<_> = it.filter(f).map(g).collect();

`count()` pour tester la vacuité

count() consomme l’itérateur en entier. Pour savoir s’il reste au moins un élément, next().is_some() ou any(...) suffisent.

`chunks` et `windows` ne sont pas des méthodes d’`Iterator`

Ce sont des méthodes de slice. Dans une chaîne d’itérateurs, il faut soit collecter au préalable, soit passer par la crate itertools.

Performance

Les itérateurs sont l’exemple canonique d’abstraction sans coût : le code généré est en pratique identique à la boucle écrite à la main, parfois meilleur — l’itérateur de slice élimine les vérifications de bornes que v[i] conserve.

Ce qui coûte réellement :

Cause	Remède
`collect()` intermédiaire	Enchaîner davantage
`clone()` dans un `map`	`into_iter()`
`Box<dyn Iterator>` dans une boucle chaude	`impl Trait`
Allocation mal dimensionnée	`Vec::with_capacity` puis `extend`

La méthode size_hint() permet à collect() de pré-réserver l’allocation. Les adaptateurs qui la préservent (map, enumerate, zip) donnent donc de meilleures allocations que ceux qui la perdent (filter, flat_map).

Tip

Comme toujours, il faut mesurer — cargo bench, criterion, perf — avant de dé-idiomatiser du code pour des raisons de performance supposées.

La crate `itertools`

Elle comble les manques de la bibliothèque standard. Les fonctions les plus utiles :

use itertools::Itertools;

it.sorted()                     // Collecte, trie, puis ré-itère
it.unique()                     // Déduplique, requiert Hash + Eq
it.chunks(3)                    // Groupes de taille fixe
it.tuple_windows()              // Fenêtres glissantes sur un Iterator
it.join(", ")                   // -> String
it.counts()                     // -> HashMap<T, usize>
it.into_group_map_by(|x| /* ... */)     // -> HashMap<K, Vec<V>>
it.collect_vec()                // Évite l'annotation de type
izip!(a, b, c)                  // zip à plus de deux itérateurs

Aide-mémoire

LE MODÈLE
  Iterator      a une méthode next()
  IntoIterator  peut devenir un Iterator      (ce qu'appelle `for`)
  FromIterator  peut être construit           (ce qu'appelle collect)

CHOISIR
  iter()        je lis, je garde la collection      -> &T
  iter_mut()    je modifie en place                 -> &mut T
  into_iter()   je consomme, je veux les valeurs    -> T
  &v / &mut v / v   dans un `for` : les mêmes trois cas

CRÉER
  iter::once / empty / repeat / repeat_with
  iter::successors(depart, f)   chaîne (parents, liens)
  iter::from_fn(closure)

TRANSFORMER (paresseux)
  map filter filter_map flat_map flatten
  take skip take_while skip_while map_while step_by
  chain zip enumerate rev cycle peekable scan inspect
  cloned copied by_ref

CONSOMMER (immédiat)
  collect for_each fold try_fold reduce
  sum product count last nth
  min max min_by_key max_by_key
  any all find find_map position partition unzip

COLLECT UTILE
  Result<Vec<T>, E>   court-circuite à la première erreur
  Option<Vec<T>>      court-circuite au premier None
  HashMap<K, V>       depuis un Iterator<Item = (K, V)>
  String              depuis des chars ou des &str

RETOURNER
  impl Iterator<Item = &T> + '_       par défaut
  Box<dyn Iterator<Item = T> + '_>    si les branches sont hétérogènes

Ressources

std::iter — la documentation du module explique le modèle mieux que la plupart des tutoriels
Iterator — parcourir une fois la liste complète des méthodes est un bon investissement
itertools — les compléments à la bibliothèque standard
Clippy détecte la plupart des pièges ci-dessus : needless_collect, map_clone, filter_map_next, into_iter_on_ref, explicit_iter_loop