Blog ENI : Toute la veille numérique !
Dernière chance (fin le 29/02) : -25€ dès 75€ sur les livres en ligne, vidéos... code FUSEE25. J'en profite !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Rust
  3. Autres collections en langage Rust
Extrait - Rust Développez des programmes robustes et sécurisés
Extraits du livre
Rust Développez des programmes robustes et sécurisés
4 avis
Revenir à la page d'achat du livre

Autres collections en langage Rust

Introduction

Le chapitre Les vecteurs en langage Rust nous a permis d’approfondir la première des collections communément utilisées en langage Rust : le vecteur. Cette collection est cependant loin d’être adaptée à toutes les situations.

Dans ce chapitre, nous allons donc procéder à l’inventaire des autres collections utilisables (et utiles) en langage Rust.

La collection VecDeque<T>

1. Présentation

Le type VecDeque est une structure définie dans std::collections. Elle correspond à un tampon circulaire et redimensionnable. Circulaire car on accède aussi facilement au début qu’à la fin de ce tampon (buffer). Redimensionnable, car à l’instar du vecteur, on peut faire varier la taille de cette collection.

VecDeque est donc ni plus ni moins qu’une file d’attente à double extrémité. En effet, le vecteur permet assez facilement de gérer une file d’attente LIFO (Last In, First Out), c’est-à-dire « dernier arrivé, premier sorti » grâce aux méthodes push et pop, particulièrement adaptées à un comportement de type pile (stack).

En revanche, si on veut modéliser une file d’attente FIFO (First In, First Out), c’est-à-dire « premier arrivé, premier sorti », le vecteur n’est plus guère adapté, ou du moins les accès sont rapidement coûteux en temps. D’où l’alternative intéressante de la collection VecDeque, qui permet de gérer la file d’attente depuis ses deux extrémités.

Représentons le fonctionnement en mémoire de la collection VecDeque :

images/11EP1.png

Représentation d’un VecDeque en mémoire...

La collection LinkedList<T>

1. Présentation

Dans une liste chaînée, on a un pointeur vers une liste d’éléments dans laquelle chaque élément pointe sur l’élément suivant et est pointé par l’élément précédent. Dans une liste doublement chaînée, chaque élément pointe à la fois sur l’élément suivant et sur l’élément précédent. De ce fait, on peut parcourir la liste d’éléments dans les deux sens.

Voici une représentation possible d’une double liste chaînée en Rust :

images/11EP2.png

Représentation d’une LinkedList<i64>

Comme on le voit dans cet exemple d’une liste doublement chaînée d’entiers, en l’occurrence une LinkedList<i64>, celle-ci est en quelque sorte composée d’un triplet :

  • Un pointeur vers le début de liste « avant ».

  • Un pointeur vers la fin de liste « arrière ».

  • La longueur (ou la taille) de la liste doublement chaînée.

Chaque élément de la liste contient sa valeur (ici une valeur entière, mais ce pourrait être une instance de structure par exemple) et un ou deux pointeurs :

  • Les deux extrémités ont un seul pointeur vers l’élément...

La collection BinaryHeap<T>

1. Présentation

Pour expliquer cette collection, il nous faut préciser ce qu’est un tas binaire. On peut voir un tas binaire comme un arbre binaire, c’est-à-dire un arbre dans lequel chaque élément a deux enfants (sauf pour les terminaisons).

Être un arbre binaire apparaît comme une condition nécessaire mais pas suffisante. L’autre condition est qu’il existe une relation d’ordre entre un nœud parent et ses deux enfants :

  • Si la relation d’ordre est « supérieur ou égal », alors le nœud parent est supérieur ou égal à ses deux enfants. On parle alors d’un tas binaire-max.

  • Si la relation d’ordre est « inférieur ou égal à », alors le nœud parent est inférieur ou égal à ses deux enfants. On parle alors d’un tas binaire-min.

C’est un type de collection particulièrement utile et performant dès lors qu’il s’agit de manipuler des files d’attente ou de priorité. En effet, il est aisé d’insérer un élément ou de rechercher le maximum ou le minimum. Nettement plus performant que si on utilisait un vecteur par exemple, ou une liste chaînée.

Voici un exemple graphique de tas binaire-max :

images/11EP3.png

Une instance de tas binaire-max

On constate qu’à chaque niveau le nœud parent est supérieur à chacun de ses deux enfants. Si c’était un tas binaire-min, alors chaque parent serait inférieur à chacun de ses deux enfants.

Lorsque l’on utilise ce type de collection en Rust se pose la question de la relation d’ordre. Peu importe le type manipulé : il suffit d’implémenter le trait Ord et de fournir une relation d’ordre entre deux instances du type choisi.

2. Utilisation de BinaryHeap<T>

Créons un projet exemple pour cette collection :

cargo new BinaryHeap --bin 
>     Created binary (application) `BinaryHeap` package 

On commence par référencer la collection que nous voulons utiliser :

use std::collections::BinaryHeap; 

Par défaut, on a un tas binaire-max. Nous verrons plus loin comment obtenir un tas binaire-min en utilisant reverse.

Créons...

Table de hachage HashMap<Key, Value>

1. Présentation

Une table de hachage est une collection qui fonctionne selon un système clé/valeur. Il y a un certain lien avec la collection « dictionnaire » qu’on peut utiliser en langage C# par exemple. C’est véritablement la performance de la recherche de valeur selon une clé donnée (le critère de recherche) qui est la principale raison de l’utilisation d’une table de hachage.

2. Utilisation de HashMap<Key, Value>

On commence par créer un projet dédié à notre petit exemple d’utilisation de la HashMap :

cargo new HashMap --bin 
>     Created binary (application) `HashMap` package 

Afin de pouvoir utiliser cette collection, on doit déjà la déclarer dans notre programme :

use std::collections::HashMap; 

Notre exemple consiste à créer un petit abécédaire des pays. À chaque lettre de l’alphabet, on associe un pays du monde. La clé est donc ici la lettre de l’alphabet, et la valeur, le nom du pays.

On crée ensuite une instance de HashMap dans laquelle on ajoute quelques paires « clé-valeur » à l’aide de la méthode insert. Pour retirer une paire, on utilise la méthode remove. Bien sûr, on peut utiliser un itérateur sur ce type de collection.

Voici le code global de l’exemple :

use std::collections::HashMap; 
 
fn main() { 
 
    let mut abecedaire_pays = HashMap::new(); 
 
    // On ajoute des paires clé-valeur dans la collection. 
    abecedaire_pays.insert( 
        "A".to_string(), ...

Approche ensembliste avec HashSet<T>

1. Présentation

La collection HashSet est similaire à un Set en langage Python. Elle correspond à une sorte d’ensemble. La grande règle qui régit ce type de collection est la suivante : « Un ensemble ne contient pas deux fois la même valeur ». Exprimé autrement : « Chaque valeur d’un ensemble n’est présente qu’une seule fois dans ledit ensemble ».

Ceci permet d’accéder facilement à des opérations logiques comme l’union entre deux ensembles, ou l’intersection. On peut également, et facilement, identifier les différences entre deux ensembles.

Voyons dès à présent comment utiliser un HashSet en langage Rust.

2. Utilisation de HashSet<T>

On commence par créer un projet dédié à notre exemple :

cargo new HashSet --bin 
>     Created binary (application) `HashSet` package 

On déclare tout d’abord la collection dont nous avons besoin :

use std::collections::HashSet; 

Puis on crée un ensemble que l’on manipule avec les méthodes habituelles. On crée un ensemble alphabet qui contient des lettres. On en créera ensuite un second. Nous pourrons alors procéder à des intersections, unions, etc.

use std::collections::HashSet; 
 
fn main() { 
 
    let mut alphabet_1 = HashSet::new(); 
 
    alphabet_1.insert("A".to_string()); 
    alphabet_1.insert("B".to_string()); 
    alphabet_1.insert("C".to_string()); 
    alphabet_1.insert("D".to_string()); 
    alphabet_1.insert("E".to_string()); 
    alphabet_1.insert("F".to_string()); 
    alphabet_1.insert("G".to_string()); 
    alphabet_1.insert("H".to_string()); 
    alphabet_1.insert("I".to_string()); 
    alphabet_1.insert("J".to_string()); 
    alphabet_1.insert("K".to_string()); 
    alphabet_1.insert("L".to_string()); ...

Conclusion

Le présent chapitre nous a permis de réaliser un inventaire de quelques collections utiles en Rust, au-delà du vecteur, largement étudié dans le chapitre précédent.

Quand on évoquait, dès le début de cet ouvrage, les intérêts de Rust, notamment en comparaison du langage C++, nous avons mentionné deux grands aspects :

  • Le contrôle supplémentaire de la gestion de la mémoire dès la compilation.

  • La gestion accrue et sécurisée des processus, surtout dans une optique multithreading, là encore dès la compilation.

C’est ce second point qui fera l’objet du chapitre Les threads et le multithreading en Rust ; mais auparavant, nous devons développer une notion utilisée dans l’écriture de threads, et entraperçue dans le chapitre Les vecteurs en langage Rust : les closures.