Les collections

Concepts

Les concepts abordés dans cet exemple sont:

Les collections

Documentation

Afin de compléter ce cours, je vous recommande la lecture des ressources suivantes :

Discussion

En Rust, comme dans la plupart des langages modernes, il existe des structures de données qui permettent de se simplifier la vie lors de l'implémentation de divers algorithmes.

Dans ce chapitre, nous allons discuter des types Vec<T>, String, des slices.

Dans ce code nous modifions que très peu le code de la partie 6 afin d'utiliser les types Vec<i32>, String et les slices.

Le type Vec<T> est une collection qui permet de stocker des données d'un type unique générique, T. Ces données sont stockées dans un espace mémoire qui est garanti d'être contigu. Cet espace mémoire peut changer dynamiquement à l'exécution contrairement aux tableaux statiques. D'un certain point de vue, on peut le considérer comme un "pointeur intelligent": un Vec est un pointeur sur le tas, qui a une certaine capacité mémoire et sait combien la mémoire sur laquelle il pointe est pleine.

Dans notre code, nous avons créé une fonction read_command_line()

/// Poorly emulates the parsing of a command line.
pub fn read_command_line(len: usize) -> Vec<i32> {
    let mut rng = rand::thread_rng();
    let mut v: Vec<i32> = Vec::new();
    for _i in 0..len {
        v.push(rng.gen());
    }
    v
}

Ici, un Vec<i32> est instancié et on ajoute des éléments aléatoires dedans à l'aide de la crate rand(). Pour créer un Vec vide, on utilise la fonction associée, qui crée un vecteur vide

#![allow(unused)]
fn main() {
    let mut v: Vec<i32> = Vec::new();
}

Ensuite, on remplit le vecteur avec des nombres aléatoires à l'aide d'une boucle for

    for _i in 0..len {
        v.push(rng.gen());
    }

qui itère sur les indices allant de 0 à len-1. Comme, nous n'utilisons pas l'indice, nous l'ignorons à l'aide de l'annotation _i. On ajoute des éléments dans le vecteur avec la fonction push() et comme nous modifions v il est primordial de noter qu'il est mut-able. Le générateur de nombre aléatoire est stocké dans une variable rng qui doit elle aussi être mutable. En effet, les générateurs de nombres aléatoires stockent en général un état interne.

Le type `String`

Une String ou un chaîne de caractère, est une séquence de caractères UTF-8. On pourrait penser naïvement que ce n'est rien d'autre qu'un Vec<char>: en fait c'est plus compliqué que cela. Bien que la chaîne de caractères, soit également rien d'autre qu'un pointeur vers des données sur le tas, ainsi qu'une variable contenant la capacité de la mémoire sur laquelle pointe le pointeur et son remplissage.

Le problème principal vient de l'encodage UTF-8: c'est un encodage de taille variable qui englobe les caractères ASCII (qui sont stockés sur un octet) et une très grande quantité d'autres caractères (l'alphabet grec, des emojis, etc.) qui sont stockés sur 1 à 4 octets. Ainsi chaque lettre de la chaîne de caractère correspond à un nombre variable d'octets (ce qui n'est pas le cas pour un Vec). Il est donc très vivement déconseillé de tenter d'indexer une String (faire s[i]) comme on le ferait avec un Vec. Il faut plutôt utiliser la méthode .get(i) qui interprète les caractères en fonction de la longueur de leurs encodages.

Une illustration de l'utilisation d'une chaîne de caractère se trouve à la fonction

/// Poorly emulates the parsing of a command line.
pub fn read_command_line_str() -> Result<Vec<i32>, String> {
    let mut s = String::from("20 10 48 58 29 0 58 -10 39 5485 394");
    s.push_str(" -100");
    s.push(' ');
    s.push('1');
    s.push('2');
    let s: Vec<&str> = s.split_ascii_whitespace().collect();

    let mut v = Vec::new();
    for i in 0..s.len() {
        v.push(
            s.get(i)
                .ok_or(String::from("Unable to index"))?
                .parse()
                .map_err(|_| format!("Unable to parse {}", s[i]))?,
        );
    }
    Ok(v)
}

Cette fonction construit une chaîne de caractères constituées de nombres et d'espaces, puis la transforme en Vec<i32> dont on calculera ensuite le minimum.

Une String est souvent construite à partir d'une "chaîne littérale" à l'aide du trait de conversion From (on les reconnaît parce qu'elles sont entourées de guillemets, "")

    let mut s = String::from("20 10 48 58 29 0 58 -10 39 5485 394");

dont le type est str formellement (c'est une chaîne de caractères qui vit durant toute la durée de vie du programme). Néanmoins, le type str n'est jamais utilisé en tant que tel en Rust, mais on utilise plutôt son "slice" &str (plus sur les "tranches" dans la section suivante).

Nous voyons que dans le code ci-dessus nous avons déclaré la variable s comme étant mutable, car ensuite nous ajoutons une slice de chaîne de caractère (de type &str) à l'aide de la fonction push_str() dans s

    s.push_str(" -100");

On peut également ajouter des char (ils sont entourés d'apostrophes ' ') à l'aide de la fonction push()

    s.push(' ');
    s.push('1');
    s.push('2');

Ensuite cette chaîne de caractères est convertie en Vec<&str> où chaque élément du Vec est un mot, qui est une sous chaîne de s.

    let s: Vec<&str> = s.split_ascii_whitespace().collect();

Finalement, dans

    let mut v = Vec::new();
    for i in 0..s.len() {
        v.push(
            s.get(i)
                .ok_or(String::from("Unable to index"))?
                .parse()
                .map_err(|_| format!("Unable to parse {}", s[i]))?,
        );
    }

on crée un nouveau Vec<i32> dans lequel on ajoute les mots convertis en entiers. On commence par itérer sur le Vec<&str> en utilisant les indices de 0 à s.len()-1 (la longueur du Vec s). Puis nous passons à la conversion à proprement parler, bien qu'on fasse des choses un peu compliquées

            s.get(i)
                .ok_or(String::from("Unable to index"))?
                .parse()
                .map_err(|_| format!("Unable to parse {}", s[i]))?,

Ici, on commence par récupérer le i-ème index de s à l'aide de la méthode get(i) qui retourne une Option<&str> (si i est un indice valide nous avons Some(s[i]), sinon None). Puis, nous transformons l'option avec ok_or() (nous encapsulons s[i] dans un Ok() si nous avons un Some() et transformons Noneen Err("Unable to index")). Ensuite nous "parsons" s[i] et retournons une erreur si le parsing échoue. Si tout s'est bien passé nous faisons donc un push() de chaque i32 et finissons par retourner le Vec<i32> encapsulé dans un Ok().

Les slices

Un slice est une "tranche" de tableau, statique ou dynamique: une référence vers un bout de mémoire et la longueur de cette mémoire.

Ainsi, si nous créons un tableau statique, nous pouvons référencer une "tranche" ou slice avec la syntaxe suivante

#![allow(unused)]
fn main() {
let a = [1, 2, 3, 4, 5, 6, 7, 8];
let b = &a[1..4]; // on pointe vers [2, 3, 4]
}

b sera donc une référence et saura que la mémoire sur laquelle elle pointe est de longueur 3 (cette information permet d'éviter les dépassements de capacité). On notera la syntaxe x..y où y est non inclus (comme pour la boucle for avec les indices). Il existe également une syntaxe sans bornes à gauche, à droite, ou à gauche et à droite.

#![allow(unused)]
fn main() {
let a = [1, 2, 3, 4, 5, 6, 7, 8];
let b = &a[1..]; // on pointe vers [2, 3, .., 8]
let b = &a[..5]; // on pointe vers [1, 2, .., 5]
let b = &a[..]; // on pointe vers [1, 2, .., 8]
}

Cette syntaxe s'applique également pour toute collection qu'on peut indexer Le type d'un slice est noté par &[T], où T est un type. On en voit un exemple lorsqu'on veut afficher un tableau par exemple

pub fn print_tab(tab: &[i32]) {
    for t in tab {
        print!("{} ", t);
    }
    println!();
}

ou encore dans la fonction find_min()

pub fn find_min<T: Minimum>(tab: &[T]) -> SomethingOrNothing<T> {
    let mut minimum = SomethingOrNothing::Nothing;
    // Here is T is Copyable. Which means that t is not moved in the loop
    for t in tab {
        minimum = minimum.min(SomethingOrNothing::Something(*t));
    }
    minimum
}

Comme on le voit dans le main() l'implémentation à l'aide d'un slice dans les fonction permet une bien plus grande généricité que si on impose un type Vec, un tableau statique, ou un slice.

// Vec
    let tab: Vec<i32> = io::read_command_line(10usize);
    println!("Among the Somethings in the list:");
    io::print_tab(&tab);
    let min = find_min(&tab);
    min.print();
// Slice
    println!("Among the Somethings in the list:");
    io::print_tab(&tab[1..9]);
    let min = find_min(&tab[1..9]);
    min.print();
// Array
    let tab = [1, 2, 3, 4, 5, 6];
    println!("Among the Somethings in the list:");
    io::print_tab(&tab);
    let min = find_min(&tab);
    min.print();

La notation &str représente ainsi une référence vers un str qui est une chaîne de caractères littérale, allouée pour la durée entière d'un programme dans une zone dédiée de la mémoire. Le type str étant "immovable" il n'est jamais utilisé tel quel, mais uniquement via des références.

Comme pour le slice utilisé pour généraliser le passage en argument des tableaux, le slice de string &str est également utilisé pour généraliser le passage de argument de chaînes de caractères.

Rustlings

Les rustlings à faire dans ce chapitre sont les suivants:

Les `Vec`

$ rustlings run vecs1
$ rustlings run vecs2

Les `String`

$ rustlings run strings1
$ rustlings run strings2
$ rustlings run strings3
$ rustlings run strings4

Rust-101: Université d'été