Algorithmes et structures de données en Rust : guide pratique

Algorithmes et structures de données en Rust : pourquoi c'est important

Rust est un langage de programmation système moderne qui combine les performances du C++ avec la sécurité mémoire assurée par le système de possession (ownership). L'étude des algorithmes et des structures de données en Rust permet non seulement de maîtriser les concepts classiques de Computer Science, mais aussi de comprendre plus profondément les caractéristiques uniques du langage : l'emprunt, les durées de vie et les abstractions à coût zéro.

Dans cet article, nous allons analyser trois structures de données fondamentales (la pile, la file d'attente et l'arbre binaire de recherche) et un algorithme classique (le tri rapide), implémentés en Rust. Chaque exemple est accompagné de code et d'explications qui vous aideront à passer de la théorie à la pratique.

1. Pile en Rust : implémentation avec Vec

La pile est une structure de données fonctionnant selon le principe LIFO (Last In, First Out). En Rust, le plus simple est d'implémenter une pile à partir du Vec standard, qui fournit toutes les méthodes nécessaires : push pour ajouter et pop pour extraire.

Cependant, pour démontrer la sécurité de Rust, nous allons créer une enveloppe avec une gestion explicite des erreurs :

pub struct Stack<T> {    elements: Vec<T>,}

impl<T> Stack<T> {    pub fn new() -> Self {        Stack { elements: Vec::new() }    }

    pub fn push(&mut self, item: T) {        self.elements.push(item);    }

    pub fn pop(&mut self) -> Option<T> {        self.elements.pop()    }

    pub fn peek(&self) -> Option<&T> {        self.elements.last()    }

    pub fn is_empty(&self) -> bool {        self.elements.is_empty()    }}

fn main() {    let mut stack = Stack::new();    stack.push(10);    stack.push(20);    stack.push(30);

    println!("Élément supérieur : {:?}", stack.peek()); // Some(30)    println!("Extraction : {:?}", stack.pop());         // Some(30)    println!("Extraction : {:?}", stack.pop());         // Some(20)    println!("La pile est vide ? {}", stack.is_empty()); // false}

L'avantage clé de Rust ici est le système de types. Si vous essayez d'extraire un élément d'une pile vide, le compilateur vous obligera à traiter Option, ce qui élimine les erreurs de déréférencement de pointeur nul, typiques du C/C++.

2. File d'attente : implémentation manuelle avec un tampon circulaire

La file d'attente (FIFO) est plus complexe que la pile car elle nécessite une suppression efficace depuis le début. Rust ne fournit pas de file bidirectionnelle prête à l'emploi avec des performances garanties, nous allons donc implémenter un tampon circulaire (circular buffer) de taille fixe.

C'est un excellent exemple pour démontrer le code unsafe et les pointeurs bruts, mais nous resterons dans la zone sécurisée en utilisant Vec et des indices :

pub struct Queue<T> {    buffer: Vec<Option<T>>,    head: usize,    tail: usize,    capacity: usize,}

impl<T> Queue<T> {    pub fn new(capacity: usize) -> Self {        let mut buffer = Vec::with_capacity(capacity);        buffer.resize_with(capacity, || None);        Queue {            buffer,            head: 0,            tail: 0,            capacity,        }    }

    pub fn enqueue(&mut self, item: T) -> Result<(), &str> {        if (self.tail + 1) % self.capacity == self.head {            return Err("La file d'attente est pleine");        }        self.buffer[self.tail] = Some(item);        self.tail = (self.tail + 1) % self.capacity;        Ok(())    }

    pub fn dequeue(&mut self) -> Option<T> {        if self.head == self.tail {            return None;        }        let item = self.buffer[self.head].take();        self.head = (self.head + 1) % self.capacity;        item    }

    pub fn is_empty(&self) -> bool {        self.head == self.tail    }}

fn main()