Trier et rechercher en Rust

Trier et rechercher sont deux tâches que vous ferez dans presque tous vos programmes : classer des joueurs par score, lister des fichiers par nom, trouver le produit le moins cher. Rust fournit aux vecteurs et aux slices (tranches) tout un ensemble de méthodes intégrées pour les deux, si bien que vous aurez rarement besoin d’écrire votre propre algorithme.

La plupart de ces méthodes prennent une closure (fonction anonyme) qui indique comment comparer deux éléments. Une fois cette idée bien assimilée, le reste de la page n’en est que des variantes.

sort et sort_unstable

.sort() range les éléments dans l’ordre croissant (le plus petit d’abord). Elle modifie le vecteur sur place, donc le vecteur doit être mut. Les nombres sont triés par valeur, les chaînes par ordre alphabétique.

fn main() {
    let mut scores = vec![42, 7, 99, 7, 15];
    scores.sort();
    println!("{:?}", scores);

    let mut names = vec!["Zoe", "adam", "Bob", "Ana"];
    names.sort_unstable();
    println!("{:?}", names);
}

Sortie :

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]

▶ Essayez par vous-même

Deux choses à remarquer :

• "adam" arrive en dernier. Les chaînes sont comparées par code de caractère, et toutes les majuscules passent avant toutes les minuscules. Triez par name.to_lowercase() (voir plus bas) si vous voulez l’ordre « du dictionnaire ». Les lettres accentuées ont le même souci : « é » passe après « z ».
• sort_unstable est généralement un peu plus rapide et n’utilise pas de mémoire supplémentaire. « Instable » ne veut pas dire bogué. Cela veut dire que deux éléments considérés comme égaux peuvent échanger leurs places. Pour de simples nombres ou chaînes, on ne voit aucune différence : c’est donc un bon choix par défaut.

Ordre décroissant

Il existe trois façons courantes de trier du plus grand au plus petit. Ici, elles donnent toutes le même résultat.

use std::cmp::Reverse;

fn main() {
    let mut a = vec![3, 8, 1, 5];
    a.sort();
    a.reverse();
    println!("{:?}", a);

    let mut b = vec![3, 8, 1, 5];
    b.sort_by(|x, y| y.cmp(x)); // y avant x = décroissant
    println!("{:?}", b);

    let mut c = vec![3, 8, 1, 5];
    c.sort_by_key(|&n| Reverse(n));
    println!("{:?}", c);
}

Sortie :

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]

▶ Essayez par vous-même

x.cmp(y) renvoie un Ordering : Less (inférieur), Equal (égal) ou Greater (supérieur). sort_by s’en sert pour décider quel élément passe en premier. Écrire y.cmp(x) inverse chaque décision, et donc tout l’ordre. Reverse est une petite enveloppe de std::cmp qui fait la même inversion pour une clé.

Trier des flottants

Essayez .sort() sur un vecteur de f64, et Rust refuse :

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0];
    prices.sort();
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
 --> src/main.rs:3:12
  |
3 |     prices.sort();
  |            ^^^^ the trait `Ord` is not implemented for `{float}`

Le compilateur vous dit que les flottants n’implémentent pas le trait Ord. Pourquoi ? .sort() a besoin d’un ordre total (le trait Ord) : pour deux valeurs quelconques, l’une doit être plus petite, égale ou plus grande que l’autre. Les flottants ont une valeur spéciale, NaN (« not a number », pas un nombre), qui n’est ni plus petite, ni égale, ni plus grande que quoi que ce soit, pas même elle-même. Les flottants n’ont donc que PartialOrd, et .partial_cmp() renvoie une Option<Ordering> qui vaut None pour NaN.

Vous avez deux bonnes solutions :

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0, 4.75];

    // Si vous êtes sûr qu'il n'y a pas de NaN :
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Fonctionne même avec NaN (NaN va à la fin) :
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Sortie :

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]

▶ Essayez par vous-même

partial_cmp(...).unwrap() provoque un panic s’il rencontre un NaN. total_cmp ne provoque jamais de panic, car il attribue une place fixe à chaque flottant, NaN compris. Préférez total_cmp, sauf si vous avez une raison de ne pas le faire.

sort_by_key et le tri de structs

sort_by_key prend une closure qui choisit selon quoi trier. C’est parfait pour les structs, où vous choisissez un champ.

#[derive(Debug)]
struct Product {
    name: String,
    price_cents: u32,
}

fn main() {
    let mut items = vec![
        Product { name: String::from("stylo"), price_cents: 150 },
        Product { name: String::from("Cahier"), price_cents: 499 },
        Product { name: String::from("gomme"), price_cents: 75 },
    ];

    items.sort_by_key(|p| p.price_cents);
    for p in &items {
        println!("{} - {}", p.price_cents, p.name);
    }

    items.sort_by_key(|p| p.name.to_lowercase());
    let names: Vec<&str> = items.iter().map(|p| p.name.as_str()).collect();
    println!("{:?}", names);
}

Sortie :

75 - gomme
150 - stylo
499 - Cahier
["Cahier", "gomme", "stylo"]

▶ Essayez par vous-même

La closure de clé doit renvoyer une valeur possédée. p.price_cents est un u32, qui est copié : pas de problème. Pour un champ String, il vous faut une nouvelle String : c’est pour ça que le second tri utilise to_lowercase(), qui en crée une. (Voir la section sur les erreurs courantes plus bas.)

Trier selon plusieurs champs

Un grand classique : trier des élèves par note, la plus haute d’abord, et quand deux élèves ont la même note, les trier par nom de A à Z. Utilisez sort_by avec .then_with(). Cette méthode ne regarde la seconde comparaison qu’en cas d’égalité sur la première.

struct Student {
    name: String,
    grade: u32,
}

fn main() {
    let mut class = vec![
        Student { name: String::from("Liam"), grade: 88 },
        Student { name: String::from("Ava"), grade: 95 },
        Student { name: String::from("Noah"), grade: 88 },
        Student { name: String::from("Emma"), grade: 88 },
        Student { name: String::from("Mia"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // note : de la plus haute à la plus basse
            .then_with(|| a.name.cmp(&b.name)) // puis nom : de A à Z
    });

    for s in &class {
        println!("{:>3}  {}", s.grade, s.name);
    }
}

Sortie :

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ Essayez par vous-même

Une variante plus courte consiste à renvoyer un tuple comme clé. Les tuples comparent le premier élément, puis le deuxième, et ainsi de suite :

class.sort_by_key(|s| (Reverse(s.grade), s.name.clone()));

Le résultat est exactement le même. C’est élégant, mais chaque nom est cloné : pour de grandes listes, sort_by avec then_with est la meilleure habitude.

Supprimer les doublons avec dedup

.dedup() supprime les éléments égaux à celui qui se trouve juste avant eux. Elle ne supprime donc tous les doublons que si la liste a d’abord été triée.

fn main() {
    let mut tags = vec!["rust", "web", "rust", "cli", "web", "web"];

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("dedup seul :   {:?}", not_sorted);

    tags.sort();
    tags.dedup();
    println!("sort + dedup : {:?}", tags);
}

Sortie :

dedup seul :   ["rust", "web", "rust", "cli", "web"]
sort + dedup : ["cli", "rust", "web"]

▶ Essayez par vous-même

Au premier essai, seuls les deux "web" placés côte à côte ont été fusionnés. Triez d’abord, puis appelez dedup. Si vous devez conserver l’ordre d’origine, utilisez l’astuce du HashSet présentée sur la page HashSet.

Rechercher : contains, position, max, min, binary_search

Voici les outils de recherche que vous utiliserez le plus :

• contains(&x) : est-ce que la valeur est là ? Renvoie un bool.
• iter().position(...) : où se trouve la première correspondance ? Renvoie une Option<usize>.
• iter().max() / iter().min() : le plus grand et le plus petit, sous forme d’Option (None pour une liste vide).
• iter().max_by_key(...) / min_by_key(...) : le plus grand ou le plus petit selon un champ.
• binary_search(&x) : une recherche très rapide, mais uniquement sur une liste triée. Renvoie Ok(index) si la valeur est trouvée, ou Err(index) qui indique où elle devrait aller.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("contient 31 ? {}", temps.contains(&31));
    println!("premier au-dessus de 20, à l'indice : {:?}", temps.iter().position(|&t| t > 20));
    println!("max : {:?}, min : {:?}", temps.iter().max(), temps.iter().min());

    let players = vec![("ana", 340), ("ben", 515), ("chen", 220)];
    let best = players.iter().max_by_key(|(_, score)| *score).unwrap();
    println!("meilleur joueur : {}", best.0);

    let mut sorted = vec![10, 20, 30, 40];
    println!("{:?}", sorted.binary_search(&30));
    let missing = sorted.binary_search(&25);
    println!("{:?}", missing);
    if let Err(pos) = missing {
        sorted.insert(pos, 25); // garde la liste triée
    }
    println!("{:?}", sorted);
}

Sortie :

contient 31 ? true
premier au-dessus de 20, à l'indice : Some(1)
max : Some(31), min : Some(12)
meilleur joueur : ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Essayez par vous-même

binary_search (recherche dichotomique) regarde l’élément du milieu, écarte la moitié qui ne peut pas contenir la valeur, et recommence. Sur une liste d’un million d’éléments, cela fait environ 20 vérifications au lieu de jusqu’à un million. La réponse Err(pos) est pratique aussi : insérer à la position pos garde la liste triée.

Attention

max() et min() ont besoin de Ord, donc elles ne fonctionnent pas non plus sur les flottants. Utilisez plutôt max_by(|a, b| a.total_cmp(b)), la même solution que pour le tri.

Erreurs courantes

Renvoyer un champ String emprunté depuis sort_by_key. Cela paraît naturel, mais ne compile pas :

students.sort_by_key(|s| s.name);

error[E0507]: cannot move out of `s.name` which is behind a shared reference
  --> src/main.rs:12:30
   |
12 |     students.sort_by_key(|s| s.name);
   |                              ^^^^^^ move occurs because `s.name` has type `String`, which does not implement the `Copy` trait

Le compilateur vous dit qu’il ne peut pas déplacer s.name hors d’une référence partagée. La closure ne fait qu’emprunter chaque élève, elle ne peut donc pas céder la String. Soit vous la clonez (|s| s.name.clone()), soit vous évitez complètement la copie avec sort_by(|a, b| a.name.cmp(&b.name)).

Utiliser binary_search sur une liste non triée. Le programme ne plante pas, mais la réponse n’a aucun sens : il peut vous dire qu’une valeur est absente alors qu’elle est bien là. Triez toujours d’abord, ou utilisez plutôt contains / position.

Exercices

1. Le classement

Vous avez des joueurs sous forme de tuples (nom, score) : ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Triez-les par score, le plus haut d’abord, en départageant les égalités par nom de A à Z. Affichez seulement les trois premiers. Indice : utilisez sort_by avec .then_with(), et une slice &players[..3] pour les trois premiers.

Voir la solution

fn main() {
    let mut players = vec![("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60)];

    players.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

    for (name, score) in &players[..3] {
        println!("{score} {name}");
    }
}

Sortie :

95 ana
88 dev
70 ben

▶ Essayez par vous-même

Dans un tuple, .0 est le nom et .1 le score. ben et chen ont tous les deux 70, donc c’est le nom qui les départage, et ben entre dans le trio de tête.

2. Le prix médian

Trouvez la médiane (la valeur du milieu) des prix 3.5, 1.25, 9.0, 4.75, 2.0. Affichez la liste triée et la médiane. Indice : triez avec total_cmp ; pour une liste de longueur impaire, l’élément du milieu est à l’indice len() / 2.

Voir la solution

fn main() {
    let mut prices: Vec<f64> = vec![3.5, 1.25, 9.0, 4.75, 2.0];

    prices.sort_by(|a, b| a.total_cmp(b));
    let median = prices[prices.len() / 2];

    println!("triés : {:?}", prices);
    println!("médiane : {median}");
}

Sortie :

triés : [1.25, 2.0, 3.5, 4.75, 9.0]
médiane : 3.5

▶ Essayez par vous-même

L’annotation de type Vec<f64> est importante. Sans elle, Rust ne sait pas encore quel type de flottant sont les nombres quand il arrive à total_cmp, et il refuse de compiler avec le message « no method named total_cmp » (aucune méthode nommée total_cmp).

Récapitulatif

• sort() et sort_unstable() trient sur place, le plus petit d’abord. Utilisez reverse(), y.cmp(x) ou Reverse pour avoir le plus grand d’abord.
• Les flottants ne peuvent pas utiliser sort() à cause de NaN. Utilisez sort_by(|a, b| a.total_cmp(b)).
• sort_by_key trie selon un champ choisi ; sort_by avec .then_with() trie selon plusieurs champs.
• dedup() ne supprime que les voisins égaux : triez d’abord.
• contains, position, max/min et max_by_key cherchent dans n’importe quelle liste ; binary_search est bien plus rapide, mais a besoin d’une liste triée.

Petit quiz

Petit quiz

1. Pourquoi vec![1.5, 0.5].sort() ne compile-t-il pas ?

On ne peut pas stocker de flottants dans un Vec sort ne fonctionne que sur des chaînes Les flottants n'implémentent pas Ord, car NaN ne peut pas être comparé Le vecteur n'est pas mut

2. Que reste-t-il dans le vecteur après vec![1, 1, 2, 1].dedup() ?

[1, 2] [1, 2, 1] [2] [1, 1, 2, 1]

3. Que renvoie vec![10, 20, 30].binary_search(&25) ?

Err(2) Ok(2) None -1

4. Dans a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)), quand le nom est-il comparé ?

Toujours, avant la note Jamais Seulement quand les noms sont différents Seulement quand les deux notes sont égales

Score : 0 / 4

Pour aller plus loin

• Slice methods: sort, sort_by, binary_search and more — documentation de la bibliothèque standard (en anglais) : toutes les méthodes de tri et de recherche, avec des notes sur la vitesse et la stabilité.
• std::cmp::Ordering — documentation de la bibliothèque standard (en anglais) : Less, Equal, Greater, ainsi que then, then_with et reverse.
• std::cmp::Reverse — documentation de la bibliothèque standard (en anglais) : l’enveloppe qui permet de trier une clé du plus grand au plus petit.
• f64::total_cmp — documentation de la bibliothèque standard (en anglais) : où se placent exactement NaN, le zéro négatif et l’infini quand vous triez des flottants.
• Sort a Vector — Rust Cookbook (en anglais) : de courtes recettes pour trier des entiers, des flottants et des structs.