Rust est-il adapté aux structures de données et aux algorithmes ?
Pour les utiliser, tout à fait : les collections standard sont rapides et bien documentées, sort est stable, et le Rust safe exclut les pointeurs pendants et les data races dès la compilation, sans ramasse-miettes. Pour écrire des structures à base de pointeurs, c'est plus difficile qu'en C ou en Java, parce que l'ownership interdit les liens partagés et mutables à moins d'opter pour Rc et RefCell, et une liste doublement chaînée ou un arbre avec des pointeurs vers le parent est fait précisément de ce genre de liens. Cette difficulté est aussi la leçon : une fois que tu sais les écrire en Rust, tu sais exactement qui possède quoi.
Quelles collections Rust correspondent à quelles structures de données ?
Vec<T> est un tableau dynamique et ta pile, VecDeque<T> un tampon circulaire et ta file, HashMap et HashSet des tables de hachage (SipHash par défaut, qui résiste aux collisions délibérées au prix d'un peu de vitesse), BTreeMap et BTreeSet des arbres B ordonnés, BinaryHeap<T> un tas-max, et LinkedList<T> une liste doublement chaînée que tu préféreras rarement à un Vec ou à un VecDeque. Il n'existe pas de type trie ou graphe ; ceux-là, tu les construis.
Pourquoi une liste chaînée est-elle si difficile à écrire en Rust ?
Parce que chaque valeur a exactement un propriétaire. Une liste simplement chaînée respecte cette règle : chaque nœud possède le suivant via Option<Box<Node>>. Une liste doublement chaînée ou un arbre avec des liens vers le parent, non, puisque deux pointeurs mènent à chaque nœud : tu te tournes alors vers Rc<RefCell<Node>>, avec Weak pour les liens arrière, ou tu gardes les nœuds dans un Vec et tu les relies par indice. Learning Rust With Entirely Too Many Linked Lists existe parce que tant de gens bloquent exactement ici.
Comment obtenir un tas-min en Rust ?
BinaryHeap<T> est un tas-max, donc enveloppe chaque élément dans std::cmp::Reverse : insère Reverse(x) et le plus petit x sort en premier. Pour Dijkstra, insère Reverse((distance, node)), et le tuple se compare d'abord par la distance. Une fois que tu as écrit un tas toi-même à l'étape deux, inverser son ordre va de soi.
Quels cours de ce parcours ne sont pas enseignés en Rust ?
Trois : la programmation dynamique et la série d'entretiens en Python, enseignées en Python, et la manipulation de bits, enseignée en C++. Ces trois cours figurent après les étapes, chacun avec un lien qui l'ouvre dans son propre langage. En Rust, une table de mémoïsation est un Vec ou une HashMap, et un dépassement d'entier provoque un panic en build de debug : une astuce sur les bits qui compte sur le rebouclage l'écrit donc explicitement avec wrapping_add ou wrapping_mul.
Faut-il connaître Rust avant de commencer ce parcours ?
Au minimum l'ownership, le borrowing, les structs, les enums et Option ; Box et les traits aident. Si c'est nouveau pour toi, le cours Rust de Coddy t'y amène d'abord, gratuitement, et ce parcours prend le relais là où il s'arrête.
