Collections#
Les collections sont des structures de données qui stockent un nombre variable d’éléments sur le tas. Contrairement aux tableaux et aux tuples dont la taille est fixée à la compilation, les collections peuvent croître et décroître à l’exécution. La bibliothèque standard de Rust fournit un ensemble riche de collections, chacune optimisée pour un profil d’accès particulier. Ce chapitre s’appuie sur les notions de possession (chapitre 5), d”Option (chapitre 9) et de traits (chapitre 13) — en particulier Eq, Hash et Ord — qui conditionnent l’utilisation de plusieurs collections.
Vec<T> : le vecteur dynamique#
Définition 85 (Vec<T>)
Un vecteur Vec<T> est un tableau dynamique contigu en mémoire, alloué sur le tas. Il gère automatiquement sa capacité : lorsque le nombre d’éléments dépasse la capacité courante, le vecteur réalloue un bloc plus grand et y déplace ses données. Vec<T> est la collection la plus utilisée en Rust.
Création, accès et modification#
// Création vide puis alimentation par push
let mut v: Vec<i32> = Vec::new();
v.push(10);
v.push(20);
v.push(30);
println!("{:?}", v);
// Création via la macro vec!
let w = vec![1, 2, 3, 4, 5];
println!("{:?}", w);
[10, 20, 30]
[1, 2, 3, 4, 5]
let mut v = vec![10, 20, 30, 40, 50];
// Indexation directe (panique si hors bornes)
println!("v[2] = {}", v[2]);
// Accès sécurisé via get, qui retourne Option<&T>
match v.get(10) {
Some(val) => println!("Trouvé : {}", val),
None => println!("Index hors bornes"),
}
// Retrait du dernier élément
let dernier = v.pop();
println!("pop : {:?}, vecteur : {:?}", dernier, v);
v[2] = 30
Index hors bornes
pop : Some(50), vecteur : [10, 20, 30, 40]
Remarque 69
L’indexation par [] panique si l’index dépasse la longueur du vecteur. En production, on préfère get() qui retourne un Option<&T> (cf. chapitre 9), permettant de traiter l’absence de valeur sans risquer une panique.
Capacité et slices#
Définition 86 (Capacité d’un Vec)
La longueur (len) est le nombre d’éléments présents. La capacité (capacity) est le nombre d’éléments que le vecteur peut contenir sans réallocation. Lorsque len dépasse capacity, le vecteur réalloue (généralement en doublant la capacité). La méthode with_capacity permet de pré-allouer afin d’éviter des réallocations coûteuses.
{
let mut v = Vec::with_capacity(10);
println!("len = {}, capacity = {}", v.len(), v.capacity());
for i in 0..10 {
v.push(i);
}
println!("len = {}, capacity = {}", v.len(), v.capacity());
// Un Vec peut être emprunté comme slice (&[T])
let tranche: &[i32] = &v[2..5];
println!("Tranche : {:?}", tranche);
}
len = 0, capacity = 10
len = 10, capacity = 10
Tranche : [2, 3, 4]
Itération#
let noms = vec!["Alice", "Bob", "Charlie"];
for nom in &noms {
println!("Bonjour, {} !", nom);
}
// Itération par référence mutable
let mut scores = vec![10, 20, 30];
for s in &mut scores { *s += 5; }
println!("Scores modifiés : {:?}", scores);
Bonjour, Alice !
Bonjour, Bob !
Bonjour, Charlie !
Scores modifiés : [15, 25, 35]
String : la chaîne de caractères dynamique#
Définition 87 (String et &str)
String est une chaîne de caractères UTF-8 dynamique, allouée sur le tas. Elle possède ses données et peut être modifiée. &str est une tranche de chaîne (string slice) : une référence immuable vers une séquence d’octets UTF-8 valide, généralement stockée dans le binaire (littéral) ou empruntée à un String.
Construction et manipulation#
// Depuis un littéral
let mut s = String::from("Bonjour");
// push_str : ajoute une tranche
s.push_str(", monde");
// push : ajoute un seul caractère
s.push('!');
println!("{}", s);
// format! : concaténation flexible
let prenom = "Ada";
let nom = "Lovelace";
let complet = format!("{} {}", prenom, nom);
println!("{}", complet);
Bonjour, monde!
Ada Lovelace
Remarque 70
L’opérateur + est défini pour String + &str, mais il consomme le String de gauche (par possession, cf. chapitre 5). Pour concaténer plusieurs fragments sans transfert de possession, la macro format! est idiomatique et plus lisible.
UTF-8, bytes et caractères#
Proposition 21 (Encodage UTF-8)
String garantit que son contenu est toujours de l’UTF-8 valide. Un caractère Unicode peut occuper de 1 à 4 octets. Par conséquent, l’indexation par position (s[i]) n’est pas autorisée sur String, car elle serait ambiguë (octets ? caractères ? grapheme clusters ?) et ne pourrait pas s’effectuer en temps constant.
let texte = String::from("résumé");
// Itération sur les bytes (octets)
print!("Bytes : ");
for b in texte.bytes() {
print!("{} ", b);
}
println!();
// Itération sur les chars (points de code Unicode)
print!("Chars : ");
for c in texte.chars() {
print!("{} ", c);
}
println!();
println!("Nombre d'octets : {}", texte.len());
println!("Nombre de chars : {}", texte.chars().count());
Bytes : 114 195 169 115 117 109 195 169
Chars : r é s u m é
Nombre d'octets : 8
Nombre de chars : 6
let s = String::from("café");
// L'indexation directe est interdite sur String
let c = s[0];
let c = s[0];
^ string indices are ranges of `usize`
the type `str` cannot be indexed by `{integer}`
help: the trait `SliceIndex<str>` is not implemented for `{integer}`
help: the following other types implement trait `SliceIndex<T>`
Remarque 71
Pour extraire une sous-chaîne, on peut utiliser un slice sur les indices d’octets (&s[0..4]), mais il faut s’assurer que les bornes tombent sur des frontières de caractères valides, sous peine de panique à l’exécution.
HashMap<K, V> : la table de hachage#
Définition 88 (HashMap<K, V>)
Un HashMap<K, V> associe des clés de type K à des valeurs de type V via une table de hachage. L’accès, l’insertion et la suppression s’effectuent en temps amorti \(O(1)\). Le type K doit implémenter les traits Eq et Hash (cf. chapitre 13).
Création et accès#
use std::collections::HashMap;
let mut capitales = HashMap::new();
capitales.insert("France", "Paris");
capitales.insert("Allemagne", "Berlin");
capitales.insert("Japon", "Tokyo");
// Accès par get (retourne Option<&V>)
match capitales.get("France") {
Some(c) => println!("Capitale de la France : {}", c),
None => println!("Pays inconnu"),
}
// Accès par indexation (panique si clé absente)
println!("Capitale du Japon : {}", capitales["Japon"]);
Capitale de la France : Paris
Capitale du Japon : Tokyo
L’API entry#
Définition 89 (API entry)
La méthode entry retourne un Entry qui représente une place dans la table — occupée ou vacante. L’appel or_insert(v) insère la valeur v uniquement si la clé est absente, puis retourne une référence mutable vers la valeur (existante ou nouvellement insérée). Ce patron évite un double accès à la table (test puis insertion).
Exemple 82 (Compteur de mots avec entry)
Voir le code ci-dessous.
use std::collections::HashMap;
let texte = "le chat le chien le chat la souris le chat";
let mut compteur = HashMap::new();
for mot in texte.split_whitespace() {
let compte = compteur.entry(mot).or_insert(0);
*compte += 1;
}
println!("{:?}", compteur);
{"le": 4, "chat": 3, "la": 1, "souris": 1, "chien": 1}
Itération#
Remarque 72
L’ordre d’itération d’un HashMap est indéterminé et peut varier d’une exécution à l’autre. Si l’on a besoin d’un ordre prévisible, on utilisera un BTreeMap.
BTreeMap<K, V> : la table ordonnée#
Définition 90 (BTreeMap<K, V>)
Un BTreeMap<K, V> est une table associative fondée sur un arbre B (B-tree). Les entrées sont toujours triées par clé. L’accès, l’insertion et la suppression s’effectuent en \(O(\log n)\). Le type K doit implémenter le trait Ord (cf. chapitre 13) au lieu de Hash.
use std::collections::BTreeMap;
let mut population = BTreeMap::new();
population.insert("Tokyo", 37_400_000u64);
population.insert("Delhi", 30_290_000);
population.insert("Shanghai", 27_060_000);
population.insert("Le Caire", 20_900_000);
// L'itération suit l'ordre lexicographique des clés
for (ville, pop) in &population {
println!("{:<12} : {} habitants", ville, pop);
}
Delhi : 30290000 habitants
Le Caire : 20900000 habitants
Shanghai : 27060000 habitants
Tokyo : 37400000 habitants
Proposition 22 (HashMap vs BTreeMap)
Critère |
|
|
|---|---|---|
Complexité moyenne |
\(O(1)\) |
\(O(\log n)\) |
Ordre des clés |
Indéterminé |
Trié (selon |
Trait requis pour |
|
|
Cas d’usage |
Accès rapide par clé |
Parcours ordonné, requêtes par intervalle |
On choisit HashMap par défaut pour les performances et BTreeMap lorsque l’ordre des clés est nécessaire.
HashSet<T> et BTreeSet<T> : les ensembles#
Définition 91 (HashSet et BTreeSet)
HashSet<T> et BTreeSet<T> sont des ensembles — des collections de valeurs uniques sans valeur associée. HashSet<T> utilise le hachage (T: Eq + Hash) ; BTreeSet<T> utilise un arbre B (T: Ord) et maintient les éléments triés. Tous deux offrent les opérations ensemblistes classiques : union, intersection, différence, différence symétrique.
Exemple 83 (Opérations ensemblistes)
Voir le code ci-dessous.
use std::collections::HashSet;
let a: HashSet<i32> = [1, 2, 3, 4, 5].iter().cloned().collect();
let b: HashSet<i32> = [3, 4, 5, 6, 7].iter().cloned().collect();
let union: HashSet<_> = a.union(&b).cloned().collect();
let intersection: HashSet<_> = a.intersection(&b).cloned().collect();
let difference: HashSet<_> = a.difference(&b).cloned().collect();
let sym_diff: HashSet<_> = a.symmetric_difference(&b).cloned().collect();
println!("A = {:?}", a);
println!("B = {:?}", b);
println!("Union = {:?}", union);
println!("Intersection = {:?}", intersection);
println!("A \\ B = {:?}", difference);
println!("A Δ B = {:?}", sym_diff);
A = {3, 1, 5, 2, 4}
B = {3, 4, 5, 6, 7}
Union = {5, 3, 6, 1, 2, 7, 4}
Intersection = {3, 4, 5}
A \ B = {2, 1}
A Δ B = {2, 7, 6, 1}
use std::collections::BTreeSet;
let mut langages = BTreeSet::new();
langages.insert("Rust");
langages.insert("Haskell");
langages.insert("OCaml");
langages.insert("Rust"); // doublon ignoré
// Itération dans l'ordre trié
for l in &langages {
print!("{} ", l);
}
println!();
println!("Contient Rust : {}", langages.contains("Rust"));
Haskell OCaml Rust
Contient Rust : true
Remarque 73
La méthode contains vérifie l’appartenance en \(O(1)\) pour HashSet et \(O(\log n)\) pour BTreeSet. C’est l’opération pour laquelle les ensembles surpassent un simple Vec, où la recherche linéaire est en \(O(n)\).
VecDeque<T> : la file à double extrémité#
Définition 92 (VecDeque<T>)
Un VecDeque<T> (double-ended queue) est un tampon circulaire alloué sur le tas. Il offre l’insertion et le retrait en \(O(1)\) amorti aux deux extrémités, contrairement à Vec qui n’est efficace qu’en fin. L’accès par index est en \(O(1)\).
use std::collections::VecDeque;
let mut file: VecDeque<&str> = VecDeque::new();
// Insertion aux deux extrémités
file.push_back("deuxième");
file.push_front("premier");
file.push_back("troisième");
println!("{:?}", file);
// Retrait depuis l'avant (FIFO)
while let Some(elem) = file.pop_front() {
println!("Traité : {}", elem);
}
["premier", "deuxième", "troisième"]
Traité : premier
Traité : deuxième
Traité : troisième
Remarque 74
VecDeque est le choix naturel pour implémenter une file d’attente (FIFO). Avec push_back et pop_front, les éléments sont traités dans l’ordre d’arrivée. On peut aussi l’utiliser comme pile (LIFO) en combinant push_back et pop_back.
BinaryHeap<T> : le tas binaire#
Définition 93 (BinaryHeap<T>)
Un BinaryHeap<T> est un tas binaire max (max-heap) : l’élément le plus grand (au sens de Ord) est toujours accessible en \(O(1)\) via peek, et le retrait du maximum s’effectue en \(O(\log n)\). L’insertion est également en \(O(\log n)\). Le type T doit implémenter Ord (cf. chapitre 13).
Exemple 84 (File de priorité)
Voir le code ci-dessous.
use std::collections::BinaryHeap;
let mut tas = BinaryHeap::new();
tas.push(5);
tas.push(1);
tas.push(10);
tas.push(3);
println!("Maximum : {:?}", tas.peek()); // Some(10)
// pop retire toujours le plus grand élément
while let Some(val) = tas.pop() {
print!("{} ", val);
}
println!();
Maximum : Some(10)
10 5 3 1
Remarque 75
BinaryHeap est un tas max par défaut. Pour obtenir un tas min (file de priorité où l’élément le plus petit sort en premier), on utilise le wrapper std::cmp::Reverse :
use std::collections::BinaryHeap;
use std::cmp::Reverse;
let mut tas_min = BinaryHeap::new();
for &v in &[5, 1, 10, 3] { tas_min.push(Reverse(v)); }
while let Some(Reverse(val)) = tas_min.pop() {
print!("{} ", val);
}
println!();
1 3 5 10
Résumé#
Les collections de la bibliothèque standard couvrent les structures de données les plus courantes :
Vec<T>est la collection par défaut pour les séquences ordonnées à taille variable.Stringest unVec<u8>garanti UTF-8, avec des contraintes d’indexation propres à l’encodage.HashMapetBTreeMapoffrent l’association clé-valeur, respectivement par hachage et par arbre ordonné.HashSetetBTreeSetmodélisent les ensembles mathématiques avec les opérations classiques.VecDequegénéralise le vecteur en autorisant l’insertion efficace aux deux extrémités.BinaryHeapfournit une file de priorité fondée sur un tas binaire max.
Toutes ces collections respectent le système de possession (chapitre 5) : elles libèrent automatiquement leur mémoire lorsqu’elles sortent de la portée. Les traits Eq, Hash et Ord (chapitre 13) déterminent quelles collections peuvent accueillir un type donné. Au chapitre suivant, nous verrons comment les itérateurs permettent de parcourir et transformer ces collections de manière expressive et performante.