Les itérateurs personnalisés en Rust

À la page Itérateurs, vous avez utilisé les itérateurs que vous fournit la bibliothèque standard : vec.iter(), .map(), .filter(), .sum(). Mais vous pouvez aussi créer vos propres itérateurs. Un compte à rebours, les nombres de Fibonacci, les pages d’un rapport, les lignes d’un format de fichier maison : tout ce qui distribue des valeurs une par une peut devenir un itérateur.

La bonne nouvelle : vous n’écrivez qu’une seule méthode, next. Rust vous donne ensuite tous les adaptateurs (map, filter, take, sum, zip et des dizaines d’autres) gratuitement. Pensez à un distributeur de tickets dans une file d’attente. Vous construisez la partie qui imprime le ticket suivant. La file, l’écran et le panneau « numéro appelé » fonctionnent tout seuls.

Votre premier itérateur : un compte à rebours

Pour faire d’un type un itérateur, implémentez le trait Iterator. Il lui faut deux choses :

• type Item : le genre de valeur que distribue l’itérateur (voyez Traits avancés pour en savoir plus sur les types associés).
• fn next(&mut self) -> Option<Self::Item> : renvoyer Some(valeur) pour la valeur suivante, ou None quand il n’y en a plus.

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None // terminé
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let mut countdown = Countdown::new(3);

    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());

    for n in Countdown::new(3) {
        println!("{}...", n);
    }
    println!("Décollage !");
}

Sortie :

Some(3)
Some(2)
Some(1)
None
None
3...
2...
1...
Décollage !

▶ Essayez par vous-même

Quelques points à remarquer :

• next prend &mut self parce qu’il modifie l’itérateur. La struct se souvient de l’endroit où elle en est (current), et chaque appel la fait avancer. C’est pour ça que countdown doit être déclaré avec let mut.
• Renvoyer None veut dire « j’ai fini ». Une boucle for appelle next encore et encore, et s’arrête au premier None.
• Notre compte à rebours continue de renvoyer None une fois terminé. C’est poli, mais le trait ne l’exige pas : certains itérateurs pourraient recommencer. Si vous avez besoin de cette garantie, appelez .fuse() sur n’importe quel itérateur.

Un itérateur sans fin : Fibonacci

Un itérateur n’est pas obligé de s’arrêter. La suite de Fibonacci (0, 1, 1, 2, 3, 5, 8, …) continue à l’infini : chaque nombre est la somme des deux précédents. L’itérateur a juste besoin de se souvenir des deux derniers nombres :

struct Fibonacci {
    current: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { current: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let value = self.current;
        // checked_add renvoie None en cas de dépassement, et `?` transmet ce None :
        // l'itérateur s'arrête au lieu de planter quand les nombres deviennent trop grands.
        let new_next = self.current.checked_add(self.next)?;
        self.current = self.next;
        self.next = new_next;
        Some(value)
    }
}

fn main() {
    let first_ten: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("{:?}", first_ten);
}

Sortie :

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ Essayez par vous-même

Tout repose sur .take(10). Sans lui, collect() essaierait de collecter la suite entière. Avec un itérateur sans fin, limitez-le toujours avec quelque chose comme take, take_while ou find.

Tous les adaptateurs, gratuitement

Voici le meilleur. Le trait Iterator a environ 75 méthodes, et toutes sauf next ont une implémentation par défaut construite à partir de next. Donc, dès que vous écrivez next, votre type peut toutes les utiliser :

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let total: u32 = Countdown::new(5).sum();
    println!("Somme : {}", total);

    let evens: Vec<u32> = Countdown::new(10).filter(|n| n % 2 == 0).collect();
    println!("Pairs : {:?}", evens);

    let labels: Vec<String> = Countdown::new(3).map(|n| format!("T-{}", n)).collect();
    println!("Étiquettes : {:?}", labels);

    let multiple = Countdown::new(100).find(|n| n % 7 == 0);
    println!("Premier multiple de 7 : {:?}", multiple);

    let pairs: Vec<(u32, char)> = Countdown::new(3).zip(['a', 'b', 'c']).collect();
    println!("Associés par zip : {:?}", pairs);
}

Sortie :

Somme : 15
Pairs : [10, 8, 6, 4, 2]
Étiquettes : ["T-3", "T-2", "T-1"]
Premier multiple de 7 : Some(98)
Associés par zip : [(3, 'a'), (2, 'b'), (1, 'c')]

▶ Essayez par vous-même

C’est un excellent exemple de ce qui rend les traits de Rust si utiles. Une petite méthode à écrire, et une énorme boîte à outils en retour.

Les itérateurs sont paresseux

Les adaptateurs comme map et take ne font rien tout seuls. Ils construisent simplement un « plan ». Le travail n’a lieu que lorsque quelque chose consomme l’itérateur : une boucle for, collect, sum, etc. Prouvons-le avec un itérateur qui affiche un message à chaque appel de next :

struct Noisy {
    n: u32,
}

impl Iterator for Noisy {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        self.n += 1;
        println!("  appel de next(), qui donne {}", self.n);
        Some(self.n)
    }
}

fn main() {
    println!("Construction de la chaîne...");
    let chain = Noisy { n: 0 }.map(|x| x * 10).take(3);
    println!("Rien n'a encore tourné. Maintenant, on consomme :");

    for value in chain {
        println!("reçu {}", value);
    }
    println!("Terminé");
}

Sortie :

Construction de la chaîne...
Rien n'a encore tourné. Maintenant, on consomme :
  appel de next(), qui donne 1
reçu 10
  appel de next(), qui donne 2
reçu 20
  appel de next(), qui donne 3
reçu 30
Terminé

▶ Essayez par vous-même

Deux leçons ici. D’abord, construire la chaîne n’a rien affiché : aucun appel à next(). Ensuite, les valeurs circulent une par une : un next, un map, un reçu, puis la valeur suivante. Il n’y a aucune liste cachée entre les étapes. Et Noisy ne s’arrête jamais, pourtant le programme se termine : après trois éléments, take(3) arrête tout simplement de demander.

Faire fonctionner votre collection dans les boucles for

Jusqu’ici, nos structs étaient des itérateurs. Mais souvent, vous avez une collection (une struct qui contient des éléments) et vous voulez qu’on puisse la parcourir, comme on parcourt un Vec. Pour cela, vous implémentez IntoIterator. C’est le trait qu’utilise une boucle for en coulisses : for x in thing appelle en réalité thing.into_iter().

Les collections offrent généralement trois façons de les parcourir, et c’est utile de les voir sur votre propre type :

Vous écrivez	Méthode derrière	Chaque élément est	La collection après coup
for s in &playlist	playlist.iter()	&String (lecture seule)	toujours utilisable
for s in &mut playlist	playlist.iter_mut()	&mut String (modifiable)	toujours utilisable
for s in playlist	playlist.into_iter()	String (possédé)	déplacée, disparue

Voici une Playlist qui gère les trois. Notre struct range ses chansons dans un Vec, donc on peut distribuer les itérateurs du Vec lui-même au lieu d’en écrire de nouveaux :

struct Playlist {
    songs: Vec<String>,
}

impl Playlist {
    fn iter(&self) -> std::slice::Iter<'_, String> {
        self.songs.iter()
    }

    fn iter_mut(&mut self) -> std::slice::IterMut<'_, String> {
        self.songs.iter_mut()
    }
}

// Fait marcher `for song in &playlist`
impl<'a> IntoIterator for &'a Playlist {
    type Item = &'a String;
    type IntoIter = std::slice::Iter<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

// Fait marcher `for song in &mut playlist`
impl<'a> IntoIterator for &'a mut Playlist {
    type Item = &'a mut String;
    type IntoIter = std::slice::IterMut<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

// Fait marcher `for song in playlist` (et consomme la playlist)
impl IntoIterator for Playlist {
    type Item = String;
    type IntoIter = std::vec::IntoIter<String>;

    fn into_iter(self) -> Self::IntoIter {
        self.songs.into_iter()
    }
}

fn main() {
    let mut playlist = Playlist {
        songs: vec![String::from("intro"), String::from("main theme"), String::from("outro")],
    };

    for song in &playlist {
        println!("Lecture : {}", song);
    }

    for song in &mut playlist {
        *song = song.to_uppercase();
    }

    println!("La plus longue : {:?}", playlist.iter().max_by_key(|s| s.len()));

    for song in playlist {
        println!("On prend : {}", song);
    }
    // `playlist` a été déplacée par la dernière boucle : on ne peut plus l'utiliser ici.
}

Sortie :

Lecture : intro
Lecture : main theme
Lecture : outro
La plus longue : Some("MAIN THEME")
On prend : INTRO
On prend : MAIN THEME
On prend : OUTRO

▶ Essayez par vous-même

Les titres des chansons restent en anglais, car max_by_key(|s| s.len()) compare des longueurs en octets, et une lettre accentuée en compte 2.

Ça fait beaucoup de lignes, mais chaque impl a la même forme : dire ce qu’est Item, dire quel type d’itérateur vous renvoyez (IntoIter), et le renvoyer. Le 'a est une lifetime (durée de vie) : il dit « les éléments empruntés vivent aussi longtemps que la playlist empruntée ». Vous pouvez recopier ce schéma pour presque n’importe quelle collection qui enveloppe un Vec.

Parcourir à l’envers et connaître la longueur

Deux traits supplémentaires méritent d’être connus. Vous n’en aurez pas besoin souvent, mais des adaptateurs comme .rev() et .len() en dépendent :

• DoubleEndedIterator ajoute next_back, qui prend les éléments par la fin. Il débloque .rev().
• ExactSizeIterator promet que l’itérateur sait exactement combien d’éléments il reste. Il débloque .len(). Vous fournissez aussi un size_hint exact dans Iterator.

// Produit low, low+1, ..., high-1 (comme l'intervalle low..high)
struct Between {
    low: u32,
    high: u32,
}

impl Iterator for Between {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        let value = self.low;
        self.low += 1;
        Some(value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let left = self.high.saturating_sub(self.low) as usize;
        (left, Some(left))
    }
}

impl DoubleEndedIterator for Between {
    fn next_back(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        self.high -= 1;
        Some(self.high)
    }
}

impl ExactSizeIterator for Between {}

fn main() {
    let backwards: Vec<u32> = Between { low: 1, high: 6 }.rev().collect();
    println!("{:?}", backwards);

    let mut both_ends = Between { low: 1, high: 6 };
    println!("début {:?}, fin {:?}", both_ends.next(), both_ends.next_back());
    println!("il en reste {}", both_ends.len());
}

Sortie :

[5, 4, 3, 2, 1]
début Some(1), fin Some(5)
il en reste 3

▶ Essayez par vous-même

Les deux extrémités avancent l’une vers l’autre, et l’itérateur est terminé quand elles se rejoignent. impl ExactSizeIterator for Between {} est vide : len() utilise le size_hint que vous avez déjà écrit.

Des raccourcis : from_fn et successors

Écrire une struct et un impl, c’est idéal pour les itérateurs que vous réutilisez. Pour un besoin ponctuel, la bibliothèque standard propose deux aides dans std::iter :

• iter::from_fn(closure) : appelle votre closure (fonction anonyme) chaque fois qu’une valeur est demandée. La closure renvoie Some(valeur) ou None, exactement comme next.
• iter::successors(premier, closure) : part d’une première valeur, et la closure calcule chaque valeur suivante à partir de la précédente. Renvoyer None arrête l’itérateur.

use std::iter;

fn main() {
    // from_fn : la closure garde son propre état (count)
    let mut count = 3;
    let countdown: Vec<u32> = iter::from_fn(|| {
        if count == 0 {
            None
        } else {
            count -= 1;
            Some(count + 1)
        }
    })
    .collect();
    println!("{:?}", countdown);

    // successors : chaque valeur est calculée à partir de la précédente
    let powers: Vec<u32> = iter::successors(Some(1u32), |&n| n.checked_mul(10)).collect();
    println!("{:?}", powers);

    // Fibonacci en une ligne : on transporte les deux derniers nombres sous forme de paire
    let fib: Vec<u64> = iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
        .take(10)
        .collect();
    println!("{:?}", fib);
}

Sortie :

[3, 2, 1]
[1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ Essayez par vous-même

powers s’arrête tout seul : la puissance de dix suivante, 10 000 000 000, ne tient pas dans un u32, donc checked_mul renvoie None et l’itérateur se termine. Une bonne règle : utilisez ces raccourcis à l’intérieur d’une seule fonction, et écrivez une struct nommée quand d’autres parties du code doivent créer l’itérateur, ou quand il a beaucoup d’état.

Erreurs courantes

Oublier mut quand vous appelez next vous-même. next modifie l’itérateur, donc la variable doit être mutable :

let countdown = Countdown { current: 3 };
println!("{:?}", countdown.next());

error[E0596]: cannot borrow `countdown` as mutable, as it is not declared as mutable
  --> src/main.rs:20:22
   |
20 |     println!("{:?}", countdown.next());
   |                      ^^^^^^^^^ cannot borrow as mutable
   |
help: consider changing this to be mutable
   |
19 |     let mut countdown = Countdown { current: 3 };
   |         +++

Le compilateur refuse d’emprunter countdown en mode mutable, puisqu’il n’a pas été déclaré mutable, et il vous montre où ajouter le mot-clé. Ajoutez donc mut. (Une boucle for n’en a pas besoin : elle prend l’itérateur et s’en occupe pour vous.)

Oublier type Item. Le trait a besoin de savoir ce que vous distribuez :

error[E0046]: not all trait items implemented, missing: `Item`
 --> src/main.rs:5:1
  |
5 | impl Iterator for Countdown {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `Item` in implementation
  |
  = help: implement the missing item: `type Item = /* Type */;`

Le message signale qu’il manque l’élément Item dans l’implémentation. Ajoutez type Item = u32; (ou le type que produit votre itérateur) à l’intérieur de l’impl.

Collecter un itérateur sans fin. Fibonacci::new().collect::<Vec<_>>() (sans take) compile sans problème, mais ne se termine jamais de façon utile : il tourne jusqu’à ce que les nombres dépassent la capacité du type, ou indéfiniment si votre next ne renvoie jamais None. Le compilateur ne peut pas détecter ce cas. Quand un itérateur risque d’être sans fin, ajoutez toujours take, take_while ou find avant de le consommer.

Récapitulatif

• Implémentez Iterator avec type Item et fn next(&mut self) -> Option<Self::Item>. Renvoyez None quand vous avez fini.
• Dès que next existe, vous obtenez gratuitement map, filter, take, sum, zip et des dizaines d’autres.
• Les itérateurs sont paresseux : rien ne se passe tant qu’une boucle for, collect, sum, etc. ne les consomme pas, et les éléments circulent un par un.
• Implémentez IntoIterator pour &MonType, &mut MonType et MonType pour permettre des boucles for qui empruntent, empruntent en mode mutable, ou consomment.
• DoubleEndedIterator permet .rev() ; ExactSizeIterator permet .len().
• Pour des itérateurs ponctuels et rapides à écrire, utilisez std::iter::from_fn ou std::iter::successors.

Petit quiz

Petit quiz

1. Que doit renvoyer next quand l'itérateur n'a plus d'éléments ?

0 Un Vec vide None Il doit faire une panic

2. Après avoir implémenté seulement next, pouvez-vous appeler .map() et .sum() sur votre itérateur ?

Oui, ce sont des méthodes par défaut construites à partir de next Non, il faut implémenter chacune d'elles Seulement si vous implémentez aussi IntoIterator

3. Dans l'exemple sur la paresse, quand next() est-il appelé pour la première fois ?

Quand on écrit .map() Quand on écrit .take(3) Quand la boucle for commence à consommer la chaîne

4. Quelle impl fait marcher for song in &playlist ?

impl Iterator for Playlist impl<'a> IntoIterator for &'a Playlist impl IntoIterator for Playlist impl DoubleEndedIterator for Playlist

5. De quel trait avez-vous besoin pour que .rev() fonctionne sur votre itérateur ?

ExactSizeIterator Clone IntoIterator DoubleEndedIterator

Score : 0 / 5

Pour aller plus loin

• Processing a Series of Items with Iterators — The Rust Book (en anglais) : comment fonctionnent Iterator et next, et pourquoi les itérateurs sont paresseux.
• Module std::iter (en anglais) : le guide officiel des itérateurs, avec une partie sur l’implémentation de vos propres itérateurs et sur IntoIterator.
• Le trait Iterator — documentation de std (en anglais) : tous les adaptateurs que vous obtenez gratuitement dès que vous écrivez next.
• Iterators — Rust by Example (en anglais) : un court exemple d’itérateur de Fibonacci à exécuter et à modifier.
• std::iter::successors (en anglais) : la documentation pour construire un itérateur à partir d’une valeur de départ et d’une règle « suivant ».