Cours de programmation séquentielle

Itérateurs

Orestis Malaspinas

Parcourir une liste

Boucles for (1/3)

On a déjà vu différentes façon de parcourir des collections:

  1. La boucle for sur un Range

    let x = vec![1, 2, 3];
    for i in 0..3 { // Range
        println!("{}", x[i]);
    }
  2. La boucle for directement sur le vecteur

    let x = vec![1, 2, 3];
    for i in x { // Vec
        println!("{}", i);
    }

Boucles for (2/3)

  • La syntaxe générale est

    for variable in expression {
        // do something
    }
  • expression est un itérateur: une série d’éléments.
  • variable prend à tour de rôle la valeur de chaque élément de l’itérateur.
  • variable peut être utilisé dans le bloc for.

Boucles for (3/3)

Sans itérateurs on écrirait quelque chose du genre

let mut i = 0;
let x = vec![1, 2, 3];
while i < 3 {
    println!("{}", x[i]);
    i += 1;
}

Les itérateurs

Généralités

  • Un itérateur est un objet sur lequel on peut appeler la méthode .next().
  • La méthode .next() est dans le trait Iterator.
  • Lorsque .next() est appelé l’itérateur retourne la prochaine valeur.
  • Il se met dans l’état “suivant”: il est modifié.
  • .next() retourne une Option<T>.

fn main() {
    let mut r = 0..3;

    println!("{:?}", r.next()); // retourne?
    println!("{:?}", r.next()); // retourne?
    println!("{:?}", r.next()); // retourne?
    println!("{:?}", r.next()); // retourne?
    println!("{:?}", r.next()); // retourne?
}

Implémentation d’un itérateur

  • La suite de Fibonacci:


n + 2 = ℱn + 1 + ℱn


#[derive(Debug)]
struct Fib {
    act: usize, // nombre actuel
    prec: usize, // nombre précédent
}

impl Iterator for Fib {
    type Item = usize; // type de retour de l'itérateur
    
    fn next(&mut self) -> Option<usize> { // next retourne une option
        let new_act = self.act + self.prec;

        self.prec = self.act;
        self.act = new_act;

        Some(self.act) // la suite de Fibonacci est infinie, donc on retourne jamais None
    }
}

fn main() {
    let mut fib = Fib{act: 1, prec: 1};
    println!("{:?}", fib.next());

    let fib4 = fib.take(4); // retourne les 4 prochains éléments de l'itérateur
    for i in fib4 {
        println!("{}", i);
    }
}

Utilisations des itérateurs

  • Un itérateur donne une séquence de valeurs.
  • Un adaptateur d’térateur (iterator adapter) qui s’applique sur un itérateur produisant un nouvel itérateur.
  • Un consommateur qui s’applique sur un adaptateur rendant un ensemble de valeurs et “détruisant” l’itérateur.

Consommateur d’itérateur

Un consommateur “consomme” un itérateur et retourne une (ou un ensemble) de valeurs. - .collect(), .find(), .fold(), …

Exemples (1/2)


fn main() {
    let v = vec![0, 4, 7, 9, 15];

    let v_iter = v.iter();
    let sum: i32 = v_iter.sum(); // l'itérateur est détruit et on a calculé la somme des éléments
    println!("La somme est un consommateur: {}", sum);
    // println!("L'itérateur: {:?}", v_iter);
}

Exemples (2/2)


fn main() {
    let v = 0..10;
    let v_vec = v.collect::<Vec<i32>>(); // l'itérateur est détruit et transformé en Vec
    println!("Iter {:?}", v_vec);
    // println!("Range {:?}", v);
}

Adaptateur d’itérateur

Un adaptateur “adapte” un itérateur et retourne un itérateur.

Exemples (1/2)

  • .map() prend une fonction anonyme (closure) en paramètre et l’applique à chaque élément.

fn main() {
    let v = vec![0, 4, 7, 9, 15];

    // iter() retourne un itérateur vers des références de v
    v.iter().map(|x| x + 1).map(|y| println!("{}", y)); // n'est pas consommé, rust ne fera rien ("lazy").
    let add_v: Vec<i32> = v.iter().map(|x| x + 1).collect();
    println!("{:?}", add_v);
}

Exemples (2/2)

  • .filter() prend prédicat et retourne un itérateur satisfaisant le prédicat.

fn main() {
    let v = vec![0, 4, 7, 9, 15];

    // into_iter() retourne un itérateur vers les valeurs de v (v disparaît)
    let fil_v: Vec<i32> = v.into_iter().filter(|x| *x > 7).collect();
    println!("{:?}", fil_v);
    // let fil_t2_v: Vec<i32> = v.into_iter().filter(|x| *x > 7).map(|y| 3*y).collect();
    // println!("{:?}", fil_v);
}