Autres collections en langage Rust

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 :

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

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 :

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 :

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 :

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 :

Voici un exemple graphique de tas binaire-max :

Une instance de tas binaire-max

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...

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(), ...

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()); ...