Collections

Posons-le d’entrée de jeu : à chaque fois que j’ai dis et je vais redire “collection” dans ce cours, en tant que programmeur C++, vous pouvez lire “conteneur”. Les deux mots ont exactement le même sens, ce sont juste des différences culturelles entre les communautés Rust et C++ qui amènent à des choix de vocabulaire un peu différents.

Ceci étant posé, faisons un petit tour des collections standard de Rust, pour voir en quoi elles diffèrent (ou pas) des conteneurs C++.

Vec

Vous avez aimé le std::vector de C++, vous allez adorer le Vec de Rust. C’est la même structure de données sous-jacentes, et les mêmes opérations de base pour modifier le contenu, la seule différence majeure c’est qu’au niveau de l’accès aux données on bénéficie aussi de l’API d’une slice Rust, qui est nettement plus riche que celle de std::vector en C++.

fn main() {
    let mut v = Vec::new();  // Création d'un vecteur vide
    v.push(42);              // Ajout d'un élément
    println!("{v:?}");

    // Création directe d'un vecteur (optimisation de l'allocation)
    v = vec![1, 2, 3];
    println!("{v:?}");

    // Création avec une certaine capacité (analogue à reserve() en C++)
    v = Vec::with_capacity(5);
    v.push(9);
    v.push(8);
    v.push(7);
    v.push(6);
    v.push(5);
    println!("{v:?}");

    // Une fois le vecteur créé, l'API est quasiment identique à celle d'un
    // tableau (ils partagent toute l'interface slice).
    // On peut faire des tranches...
    let s = &v[1..3];
    println!("{s:?}");

    // ...et on peut construire un vecteur ayant le même contenu (possible avec
    // toute slice, je ne l'avais pas encore évoqué).
    let owned_s = s.to_owned();
    println!("{owned_s:?}");

    // ...et on peut itérer, la seule forme d'itération qui se comporte de façon
    // inhabituelle étant l'itération par valeur...
    for (idx, elem) in v.into_iter().enumerate() {
        println!("Element {idx} : {elem}");
    }

    // ...parce que comme Vec gère une allocation mémoire, il n'est pas copiable.
    // Donc après un mouvement, la valeur Vec<u32> n'est plus utilisable, bien
    // que u32 en lui même soit copiable.
    // Et donc ce code là ne compilerait pas après into_iter(), car v a été
    // déplacé dans l'itérateur ci-dessus :
    /* println!("{v:?}"); */
}

La syntaxe des génériques en Rust est la même qu’en C++ (on reviendra dessus ultérieurement), donc le type d’un vecteur d’éléments de types T est Vec<T>.

N’hésitez pas à lire attentivement la documentation de Vec, et à relire celle de slice. La plupart des opérations que vous allez vouloir effectuer sur des Vec au début de votre apprentissage de Rust existent déjà dans la bibliothèque standard, et leur implémentation est souvent plus intelligente que la première idée qui vous viendra à l’esprit.

String

De la même façon que str est une forme spécialisée de [u8] avec l’invariant de type supplémentaire que le contenu est une séquence UTF-8 valide, String est une forme spécialisée de Vec<u8> possédant ce même invariant.

L’invariant “doit rester une séquence UTF-8” valide a des conséquences sur l’interface de modification, qui est exprimée en termes d’ajout et suppression de points de code (char), et pas d’octets individuels.

En dehors de ça, on peut dire que String est à Vec<u8> ce que str est à [u8], et à partir de là tout ce qu’on apprend de Vec et [u8] peut souvent être transposé à String et str avec des modifications mineures. Et encore une fois, mon conseil reste : étudiez soigneusement la documentation de String et str et utilisez les implémentations de la bibliothèque standard chaque fois que c’est possible.

Autres collections

Vous avez peut-être remarqué qu’en C++, std::vector et std::string sont des conteneurs ayant une place à part : dans un programme C++ typique, on trouve beaucoup plus d’objets de ces types que de tous les autres types conteneurs réunis.

C’est normal : le tableau est une structure de données très fondamentale, en accord étroit avec les réalités du matériel, qui est extrêmement efficace pour un grand nombre d’opérations. Si on n’a pas de raisons d’utiliser autre chose qu’un tableau, c’est une excellente structure de données par défaut.

Rust prend acte de cet état de fait et traite les types tableaux et chaînes de façon spéciale en les plaçant d’autorité dans le scope global. Pour toutes les autres collections, il faut faire son marché dans le module std::collections de la bibliothèque standard, et si on ne veut pas taper leur chemin complet, il faut les importer explicitement avec des instructions comme use std::collections::VecDeque (nous reviendrons sur ce point quand nous aborderons les modules).

Séquences

Dans le module std::collections, on trouve d’abord un certain nombre de structures de données dont la sémantique est essentiellement séquentielle : les données sont rangées dans un certain ordre, et la notion d’ordre est omniprésente dans l’interface.

• VecDeque est une file à double entrée basée sur un Vec : on peut insérer ou enlever des éléments au début et à la fin, et en interne c’est implémenté avec un buffer circulaire qui rend ces deux opérations très efficace. Ce type de structure de données est omniprésent dès qu’on veut ordonnancer le traitement de tâches ou traiter des données en flux tendu, c’est donc très bien d’en avoir une implémentation standard sous la main dans ce genre de cas.

  #![allow(unused)]
  fn main() {
  use std::collections::VecDeque;
  
  let mut fifo = VecDeque::from([9, 8, 7, 6]);
  fifo.push_front(1);
  fifo.push_back(2);
  
  println!("{fifo:?}");
  println!("{:?}", fifo.pop_front());
  println!("{fifo:?}");
  }

• BinaryHeap est une file d’attente avec priorités basée sur un tas binaire : on insère des éléments avec une relation d’ordre entre eux, et à tout moment on peut extraire le plus grand élément. Comme VecDeque, c’est une structure de données très utile dans les problèmes d’ordonnancement : en théorie de l’ordonnancement VecDeque correspond à la politique d’ordonnancement FIFO, là où BinaryHeap correspond à l’ordonnancement avec priorités.

  #![allow(unused)]
  fn main() {
  use std::collections::BinaryHeap;
  
  let mut heap = BinaryHeap::new();
  heap.push(1);
  heap.push(4);
  heap.push(2);
  
  println!("{:?}", heap.pop());
  println!("{:?}", heap.pop());
  }

• LinkedList est une liste chaînée, une structure de données omniprésente dans les cours d’informatique car elle a plein d’excellentes propriétés sur le plan théorique. Toutefois, dans la vraie vie, elle a des performances désastreuse pour presque tous les cas d’utilisation (la seule exception étant l’ajout d’éléments en milieu de liste quand on connaît déjà un des voisins). Je vous recommanderais donc de ne l’utiliser qu’après très mûre réflexion.

Associations

En plus de collections séquentielles, std::collections fournit aussi des collections associatives, qui permettent d’établir un lien entre des objets d’un type clé K et un type valeur V, à la manière de std::map et std::unordered_map en C++. On s’en sert pour faire ce genre de choses :

#![allow(unused)]
fn main() {
use std::collections::HashMap;

let mut user_ids = HashMap::new();
user_ids.insert("Hadrien", 123);
user_ids.insert("Pierre", 456);

println!("{user_ids:?}");
println!("Hadrien a l'ID {}", user_ids["Hadrien"]);
println!("Pierre a l'ID {}", user_ids["Pierre"]);
}

Ici, on utilise la structure de données associative comme une sorte de struct définie à l’exécution. On peut aussi s’en servir comme un tableau dont tous les indices ne sont pas alloués. C’est extrêmement flexible, le domaine d’application est très large.

Pour rechercher une clé de façon efficace, sans avoir à examiner toutes les clés une par une, une structure de données associative exploite les propriétés du type clé. Deux propriétés sont couramment utilisées :

• Soit on possède une fonction de hachage qui, partant d’une clé, produit un petit nombre entier (le hash) tel que deux clés différentes ont une probabilité très faible d’avoir le même hash. Cela réduit grandement le nombre de clés qu’on doit examiner pour retrouver la valeur, qui ne dépend en théorie pas du nombre de couples (clés, valeurs) stockées. C’est le principe utilisé par HashMap, qui est analogue à std::unordered_map en C++.
• Soit on exploite le fait que le type clé est ordonné et on range les clés selon un arbre de tri (red-black tree, B-tree…) pour permettre une recherche de clé en O(log(N)) étapes où N est le nombre d’élément dans la structure de données. Cette structure de données peut être intéressante sur des clés qui sont beaucoup plus efficaces à comparer qu’à hacher, quand le nombre de valeurs n’est pas trop grand, ou quand il n’y a pas de fonction de hachage évidente. C’est le principe de BTreeMap en Rust, qui est analogue à std::map en C++.

Ensembles

Une fois qu’on a une collection associative, on peut trivialement implémenter une collection ensembliste qui contient des valeurs d’un type K et permet de savoir rapidement si une valeur est où non présente dans la collection. Il suffit de construire une collection associatif dont le type valeur est () : on a des clés, mais pas de valeur associée, on exploite juste la recherche de clé optimisée fournie par la collection associative sous-jacente.

Néanmoins, les collections ensemblistes sont en pratique utilisés de façon différente par les utilisateurs, avec des opérations plutôt issues de la théorie des ensembles : union, intersection, différence symétrique… Il est donc utile de fournir une interface dédiée pour ces opérations, et c’est ce que font HashSet et BTreeSet, respectivement basés sur HashMap et BTreeMap.

#![allow(unused)]
fn main() {
use std::collections::HashSet;

let mut set1 = HashSet::new();
set1.insert(123usize);
set1.insert(456);
set1.insert(789);

println!("{}", set1.contains(&123));
println!("{}", set1.contains(&42));
println!();

let set2 = HashSet::from([24usize, 42]);

// Notez que l'itération sur HashSet produit les données en ordre arbitraire
for elem in set1.union(&set2) {
    println!("{elem}");
}
}

Construction depuis un itérateur

Quand on a un itérateur de valeurs, on peut trivialement construire une collection de valeurs de ce type avec l’opération collect() de l’itérateur :

#![allow(unused)]
fn main() {
let v =
    (0..50)                        // Itération sur les nombres 0 <= i < 50
        .filter(|i| *i % 3 == 0)   // Sélection des multiples de 3
        .map(|i| 42 * i)           // Multiplication par 42
        .collect::<Vec<usize>>();  // Construction d'un vecteur de usize
println!("{v:#?}");
}

Outre l’élégance du formalisme, cette manière de construire une collection a l’avantage que lorsque la taille de l’itérateur est connue à l’avance, elle peut être transmise à l’implémentation de la collection pour optimiser automatiquement l’allocation mémoire. Utilisez-la donc chaque fois que la liste des éléments de la collection s’exprime bien sous la forme d’un pipeline d’itérateurs.

Les collections associatives se construisent à partir d’un itérateur de tuples (clé, valeur), pour le reste leur fonctionnement est identique à celui des autres collectionss du point de vue de collect().

Puisqu’il existe un grand nombre de collections ayant des éléments d’un certain type, le type émis par collect() ne peut pas être inféré et doit toujours être spécifié explicitement. Il y a deux manières courantes de procéder :

#![allow(unused)]
fn main() {
// Typer la variable de destination
let v: Vec<u32> = (0..100).collect();
println!("{v:?}");

// Typer l'opération collect()
let v = (0..100).collect::<Vec<u32>>();
println!("{v:?}");
}

La sémantique est parfaitement équivalente, le choix entre les deux est une pure question de goût personnel. Personnellement, je trouve la seconde forme plus lisible sur des gros pipelines, car elle évite de devoir remonter le regard vers le haut de la déclaration pour savoir ce que collect() va produire. Mais je suis sensible à l’argument que la deuxième version a une syntaxe nettement plus lourde, qui peut sembler excessive à petite échelle.