Itérateurs

Itérateurs#

Les itérateurs sont au coeur du style idiomatique en Rust. Ils fournissent une abstraction unifiée pour parcourir des séquences d’éléments — qu’il s’agisse de collections en mémoire, de plages numériques ou de flux calculés à la demande. Grâce à l’évaluation paresseuse et à la monomorphisation (cf. chapitre 14), les chaînes d’itérateurs offrent des performances comparables à celles de boucles manuelles, tout en améliorant la lisibilité et la composabilité du code. Ce chapitre s’appuie sur les traits (chapitre 13), les génériques et les types associés (chapitre 14), ainsi que sur les collections de la bibliothèque standard (chapitre 15).

Le trait Iterator#

Définition 94 (Le trait Iterator)

Le trait Iterator est défini dans std::iter. Il comporte un type associé Item, qui désigne le type des éléments produits, et une unique méthode requise, next, qui retourne Option<Self::Item> : Some(valeur) pour chaque élément, puis None lorsque la séquence est épuisée.

La signature simplifiée du trait est la suivante :

// Signature simplifiée (la vraie définition fournit des dizaines de méthodes par défaut)
trait Iterateur {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

Toutes les autres méthodes du trait (map, filter, collect, etc.) possèdent des implémentations par défaut construites à partir de next. Implémenter next suffit donc à obtenir l’ensemble de l’API.

Exemple 85 (Utilisation directe de next)

Voir le code ci-dessous.

{
let v = vec![10, 20, 30];
let mut it = v.iter();

println!("{:?}", it.next()); // Some(10)
println!("{:?}", it.next()); // Some(20)
println!("{:?}", it.next()); // Some(30)
println!("{:?}", it.next()); // None
}

Some(10)

Some(20)

Some(30)

None

()

L’itérateur est consommé progressivement : chaque appel à next fait avancer le curseur interne. L’itérateur doit être déclaré mut car son état change à chaque appel.

Créer des itérateurs#

Les collections de la bibliothèque standard proposent trois méthodes principales pour obtenir un itérateur, qui diffèrent par le mode de possession des éléments.

Définition 95 (iter, iter_mut et into_iter)

  • iter() produit un itérateur sur des références partagées (&T). La collection n’est pas consommée.

  • iter_mut() produit un itérateur sur des références mutables (&mut T). La collection n’est pas consommée mais peut être modifiée élément par élément.

  • into_iter() consomme la collection et produit un itérateur sur les valeurs possédées (T).

Exemple 86 (Les trois modes d’itération)

Voir le code ci-dessous.

{
let noms = vec![String::from("Alice"), String::from("Bob"), String::from("Clara")];

// iter() : emprunte la collection
for nom in noms.iter() {
    println!("Bonjour, {} !", nom); // nom est de type &String
}
println!("La collection est toujours accessible : {:?}", noms);
}

Bonjour, Alice !

Bonjour, Bob !

Bonjour, Clara !

La collection est toujours accessible : ["Alice", "Bob", "Clara"]

()

let mut scores = vec![10, 20, 30];

// iter_mut() : emprunte la collection de manière mutable
for s in scores.iter_mut() {
    *s += 5; // s est de type &mut i32
}
println!("Scores modifiés : {:?}", scores);

Scores modifiés : [15, 25, 35]

let couleurs = vec![String::from("rouge"), String::from("vert"), String::from("bleu")];

// into_iter() : consomme la collection
for c in couleurs.into_iter() {
    println!("Couleur possédée : {}", c); // c est de type String
}
// couleurs n'est plus utilisable ici

Couleur possédée : rouge

Couleur possédée : vert

Couleur possédée : bleu

()

Remarque 76

La boucle for x in collection appelle implicitement into_iter() sur la collection. Pour itérer par référence, on écrit for x in &collection (équivalent de iter()) ou for x in &mut collection (équivalent de iter_mut()). Ce comportement est régi par le trait IntoIterator, détaillé plus loin.

Adaptateurs#

Les adaptateurs sont des méthodes qui transforment un itérateur en un autre itérateur. Ils sont paresseux : aucun calcul n’est effectué tant qu’un consommateur n’est pas appelé.

Définition 96 (Adaptateur d’itérateur)

Un adaptateur (iterator adaptor) est une méthode sur Iterator qui retourne un nouvel itérateur. L’itérateur résultant encapsule l’itérateur d’origine et applique une transformation à chaque élément produit.

map et filter#

{
let nombres = vec![1, 2, 3, 4, 5, 6];

let pairs_au_carre: Vec<i32> = nombres.iter()
    .filter(|&&x| x % 2 == 0)   // ne garde que les pairs
    .map(|&x| x * x)             // élève au carré
    .collect();

println!("{:?}", pairs_au_carre); // [4, 16, 36]
}

[4, 16, 36]

()

enumerate et zip#

let fruits = vec!["pomme", "banane", "cerise"];

// enumerate : ajoute l'indice
for (i, fruit) in fruits.iter().enumerate() {
    println!("{}: {}", i, fruit);
}

0: pomme

1: banane

2: cerise

()

{
let noms = vec!["Alice", "Bob", "Clara"];
let ages = vec![30, 25, 28];

// zip : associe les éléments deux à deux
let annuaire: Vec<_> = noms.iter().zip(ages.iter()).collect();
println!("{:?}", annuaire);
}

[("Alice", 30), ("Bob", 25), ("Clara", 28)]

()

chain, take, skip#

{
let a = vec![1, 2, 3];
let b = vec![4, 5, 6];

// chain : concatène deux itérateurs
let tout: Vec<&i32> = a.iter().chain(b.iter()).collect();
println!("chain : {:?}", tout);

// take : ne garde que les n premiers éléments
let debut: Vec<&i32> = a.iter().chain(b.iter()).take(4).collect();
println!("take(4) : {:?}", debut);

// skip : saute les n premiers éléments
let fin: Vec<&i32> = a.iter().chain(b.iter()).skip(2).collect();
println!("skip(2) : {:?}", fin);
}

chain : [1, 2, 3, 4, 5, 6]

take(4) : [1, 2, 3, 4]

skip(2) : [3, 4, 5, 6]

()

flatten et peekable#

{
let matrice = vec![vec![1, 2], vec![3, 4], vec![5, 6]];

// flatten : aplatit un itérateur d'itérateurs
let plat: Vec<i32> = matrice.into_iter().flatten().collect();
println!("flatten : {:?}", plat);
}

flatten : [1, 2, 3, 4, 5, 6]

()

{
let donnees = vec![1, 2, 3];
let mut it = donnees.iter().peekable();

// peekable : permet de regarder le prochain élément sans le consommer
println!("peek : {:?}", it.peek()); // Some(1)
println!("next : {:?}", it.next()); // Some(1)
println!("peek : {:?}", it.peek()); // Some(2)
}

peek : Some(1)

next : Some(1)

peek : Some(2)

()

Consommateurs#

Les consommateurs sont des méthodes qui déclenchent le parcours effectif de l’itérateur et produisent une valeur finale.

Définition 97 (Consommateur d’itérateur)

Un consommateur (consuming adaptor) est une méthode sur Iterator qui consomme l’itérateur en appelant next de manière répétée et retourne une valeur agrégée (un scalaire, une collection, un booléen, etc.).

collect, sum, count#

let plage: Vec<i32> = (1..=10).collect();
println!("collect : {:?}", plage);

let total: i32 = (1..=10).sum();
println!("sum : {}", total);

let n = (1..=10).filter(|x| x % 3 == 0).count();
println!("count (multiples de 3) : {}", n);

collect : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

sum : 55

count (multiples de 3) : 3

any, all, find#

{
let nombres = vec![2, 4, 6, 8, 10];

println!("any impair ? {}", nombres.iter().any(|&x| x % 2 != 0));
println!("all pairs ? {}", nombres.iter().all(|&x| x % 2 == 0));

let premier_sup_5 = nombres.iter().find(|&&x| x > 5);
println!("find > 5 : {:?}", premier_sup_5);
}

any impair ? false

all pairs ? true

find > 5 : Some(6)

()

fold et for_each#

// fold : réduit l'itérateur à une valeur unique avec un accumulateur
let produit = (1..=5).fold(1, |acc, x| acc * x);
println!("5! = {}", produit);

// for_each : applique un effet de bord à chaque élément
(1..=5).for_each(|x| print!("{} ", x));
println!();

5! = 120

1 2 3 4 5

max et min#

let valeurs = vec![38, 12, 57, 4, 91, 23];

println!("max : {:?}", valeurs.iter().max());
println!("min : {:?}", valeurs.iter().min());

max : Some(91)

min : Some(4)

Remarque 77

max et min retournent Option<&T> car l’itérateur peut être vide. Pour les types à virgule flottante qui n’implémentent pas Ord (en raison de NaN), on utilise fold ou reduce avec f64::max / f64::min.

Évaluation paresseuse#

Proposition 23 (Paresse des adaptateurs)

Les adaptateurs d’itérateurs sont paresseux (lazy) : ils ne produisent aucun élément tant qu’un consommateur ne les sollicite pas. Construire une chaîne d’adaptateurs sans consommateur ne déclenche aucun calcul et provoque un avertissement du compilateur.

{
let v = vec![1, 2, 3, 4, 5];

// Sans consommateur : aucun calcul n'est effectué
let _paresseux = v.iter().map(|x| { println!("traité : {}", x); x * 2 });
println!("Aucun élément n'a été traité.");

// Avec un consommateur : le calcul se déclenche
let resultats: Vec<_> = v.iter().map(|x| { println!("traité : {}", x); x * 2 }).collect();
println!("Résultats : {:?}", resultats);
}

Aucun élément n'a été traité.

traité : 1

traité : 2

traité : 3

traité : 4

traité : 5

Résultats : [2, 4, 6, 8, 10]

()

Remarque 78

L’évaluation paresseuse présente un avantage majeur en termes de performances : les éléments sont traités un par un à travers toute la chaîne, sans créer de collections intermédiaires. Une chaîne .filter().map().take(3).collect() ne parcourt que les éléments strictement nécessaires pour produire les trois résultats demandés.

Le trait IntoIterator#

Définition 98 (IntoIterator)

Le trait IntoIterator définit une méthode into_iter(self) qui convertit une valeur en itérateur. Tout type implémentant IntoIterator peut être utilisé directement dans une boucle for. Le compilateur transforme for x in valeur en un appel à valeur.into_iter() suivi d’appels successifs à next.

Proposition 24 (Desugaring de la boucle for)

La boucle for element in expression { corps } est transformée par le compilateur en :
let mut iter = IntoIterator::into_iter(expression);
while let Some(element) = iter.next() { corps }
Tout type implémentant IntoIterator est donc compatible avec for.

Les collections standard implémentent IntoIterator pour trois cibles :

  • impl IntoIterator for Vec<T> (consomme le vecteur, produit T)

  • impl IntoIterator for &Vec<T> (emprunte, produit &T)

  • impl IntoIterator for &mut Vec<T> (emprunte mutuellement, produit &mut T)

Exemple 87 (Implémentation personnalisée de IntoIterator)

Voir le code ci-dessous.

struct Plage {
    debut: i32,
    fin: i32,
}

struct PlageIter {
    courant: i32,
    fin: i32,
}

impl Iterator for PlageIter {
    type Item = i32;
    fn next(&mut self) -> Option<i32> {
        if self.courant < self.fin {
            let val = self.courant;
            self.courant += 1;
            Some(val)
        } else {
            None
        }
    }
}

impl IntoIterator for Plage {
    type Item = i32;
    type IntoIter = PlageIter;

    fn into_iter(self) -> PlageIter {
        PlageIter { courant: self.debut, fin: self.fin }
    }
}

// Utilisable directement dans une boucle for
for x in (Plage { debut: 3, fin: 7 }) {
    print!("{} ", x);
}
println!();

3 4 5 6

Itérateurs personnalisés#

Implémenter le trait Iterator pour un type maison permet de créer des séquences sur mesure, potentiellement infinies, bénéficiant de toute l’API standard (adaptateurs, consommateurs).

Définition 99 (Itérateur personnalisé)

Pour créer un itérateur personnalisé, on définit une structure portant l’état de l’itération, puis on implémente Iterator en fournissant le type associé Item et la méthode next. La séquence se termine lorsque next retourne None.

Exemple 88 (Suite de Fibonacci)

Voir le code ci-dessous.

struct Fibonacci {
    a: u64,
    b: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Self { a: 0, b: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let valeur = self.a;
        let nouveau = self.a + self.b;
        self.a = self.b;
        self.b = nouveau;
        Some(valeur) // itérateur infini : ne retourne jamais None
    }
}

// Les 10 premiers termes de la suite de Fibonacci
let termes: Vec<u64> = Fibonacci::new().take(10).collect();
println!("{:?}", termes);

// Somme des termes inférieurs à 1000
let somme: u64 = Fibonacci::new()
    .take_while(|&x| x < 1000)
    .sum();
println!("Somme des termes < 1000 : {}", somme);

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

Somme des termes < 1000 : 2583

Remarque 79

Un itérateur qui ne retourne jamais None est un itérateur infini. Il est parfaitement utilisable en Rust grâce à l’évaluation paresseuse, à condition d’employer un consommateur limitant comme take, take_while ou find. Appeler collect sur un itérateur infini provoquerait un dépassement de mémoire.

Résumé#

Les itérateurs en Rust forment un système cohérent articulé autour de quelques principes :

  1. Le trait Iterator ne requiert qu’une seule méthode (next) et fournit des dizaines de méthodes par défaut grâce aux implémentations par défaut du trait (chapitre 13).

  2. Les adaptateurs (map, filter, zip, etc.) composent les transformations de manière déclarative, sans allocation intermédiaire.

  3. Les consommateurs (collect, sum, fold, etc.) déclenchent le calcul effectif grâce à l’évaluation paresseuse.

  4. Le trait IntoIterator unifie la syntaxe de la boucle for et permet à tout type de devenir itérable.

  5. La monomorphisation (chapitre 14) garantit que les chaînes d’itérateurs sont compilées en code machine aussi efficace que des boucles écrites à la main : c’est le principe des abstractions à coût zéro.

La maîtrise des itérateurs est essentielle pour écrire du Rust idiomatique. Ils remplacent avantageusement les boucles explicites avec indices dans la grande majorité des cas, en offrant une expression plus concise, plus sûre et tout aussi performante.

Contenu