Algorithmes et structures de données en Rust : guide pour débutants

Algorithmes et structures de données en Rust : guide complet pour débutants

Rust est un langage de programmation qui allie les hautes performances du C/C++ à la sécurité mémoire garantie à la compilation. Pour les développeurs débutants, l'étude des algorithmes et des structures de données en Rust est non seulement un moyen de maîtriser les concepts fondamentaux de l'informatique, mais aussi une opportunité de comprendre les particularités uniques du langage : la possession (ownership), l'emprunt (borrowing) et les durées de vie (lifetimes).

Dans cet article, nous allons passer en revue les structures de données et les algorithmes clés que tout développeur devrait connaître. Tous les exemples de code sont écrits en Rust et prêts à être exécutés. Nous commencerons par les structures de base fournies par la bibliothèque standard, puis nous passerons à l'implémentation d'algorithmes classiques.

1. Structures de données de base en Rust

La bibliothèque standard de Rust (std) fournit un riche ensemble de structures de données prêtes à l'emploi. Examinons les trois plus importantes.

Vecteurs (Vec)

Vec est un tableau dynamique qui peut modifier sa taille. C'est l'équivalent d'ArrayList en Java ou de list en Python. Les vecteurs garantissent un placement contigu des éléments en mémoire, ce qui rend l'accès par index très rapide (O(1)).

fn main() {    // Création d'un vecteur vide    let mut numbers: Vec<i32> = Vec::new();        // Ajout d'éléments    numbers.push(10);    numbers.push(20);    numbers.push(30);        // Accès par index    let first = numbers[0]; // 10        // Itération    for num in &numbers {        println!("{}", num);    }        // Macro vec!    let fruits = vec!["pomme", "banane", "cerise"];    println!("Deuxième fruit : {}", fruits[1]); // banane}

Tables de hachage (HashMap)

HashMap est une structure de données qui stocke des paires clé-valeur. Elle offre un temps d'accès moyen O(1) pour l'insertion, la recherche et la suppression. Idéale pour les tâches nécessitant une recherche rapide par clé.

use std::collections::HashMap;

fn main() {    let mut scores = HashMap::new();        scores.insert(String::from("Alice"), 100);    scores.insert(String::from("Bob"), 85);        // Obtention de la valeur par clé    let alice_score = scores.get(&String::from("Alice"));    match alice_score {        Some(score) => println!("Alice a obtenu : {}", score),        None => println!("Alice non trouvée"),    }        // Parcours de toutes les paires    for (name, score) in &scores {        println!("{} : {}", name, score);    }}

Chaînes de caractères (String)

En Rust, il existe deux types principaux de chaînes : &str (tranche de chaîne) et String (chaîne mutable et possédante). Travailler avec les chaînes en Rust nécessite de l'attention en raison du codage UTF-8.

fn main() {    let mut hello = String::from("Bonjour, ");    hello.push_str("le monde !"); // Ajout d'une chaîne    hello.push('!'); // Ajout d'un caractère        println!("{}", hello); // Bonjour, le monde !!         // Tranches de chaîne (attention aux limites des caractères !)    let slice = &hello[0..8]; // "Bonjour"    println!("Tranche : {}", slice);}

2. Implémentation de la pile et de la file d'attente

La pile et la file d'attente sont des structures de données fondamentales souvent utilisées dans les algorithmes. En Rust, elles peuvent être facilement implémentées à l'aide de Vec.

Pile (LIFO — Last In, First Out)

La pile fonctionne selon le principe "dernier arrivé, premier sorti". Vec fournit déjà les méthodes push et pop, qui implémentent le comportement d'une pile.

fn main() {    let mut stack: Vec<i32> = Vec::new();        stack.push(1);    stack.push(2);    stack.push(3);        while let Some(top) = stack.pop() {        println!("Extraction : {}", top);    }    // Sortie : 3, 2, 1}

File d'attente (FIFO — First In, First Out