--- title: "Comment supprimer efficacement les doublons d'un Vec où T: Eq + Hash ?" description: "Approches efficaces pour supprimer les doublons d'un Vec où T: Eq + Hash, comparant les méthodes basées sur HashSet et le tri avec analyse de performance" url: "https://mayorana.ch/fr/blog/efficient-duplicate-removal-vec" language: "fr" date: "2025-10-28" author: "Mohamed Bennekrouf" tags: - "rust" - "collections" - "vec" - "deduplication" - "hashset" - "performance" en_version: "https://mayorana.ch/en/blog/efficient-duplicate-removal-vec.md" --- # Comment supprimer efficacement les doublons d'un Vec où T: Eq + Hash ? ## Approches efficaces Lorsque T implémente Eq + Hash (pour les vérifications d'égalité et le hachage), les méthodes optimales sont :

## 1. Utilisation de HashSet (préserve l'ordre) ### Étapes : 1. Parcourir le Vec. 2. Suivre les éléments déjà vus avec un HashSet. 3. Collecter uniquement les éléments non vus. ### Code : ```rust use std::collections::HashSet; fn dedup_ordered(vec: &mut Vec) { let mut seen = HashSet::new(); vec.retain(|x| seen.insert(x.clone())); } ``` ### Exemple : ```rust let mut vec = vec![1, 2, 2, 3, 3, 3]; dedup_ordered(&mut vec); assert_eq!(vec, [1, 2, 3]); // Ordre préservé ``` L'astuce : `HashSet::insert` renvoie `false` quand la valeur était déjà présente, c'est exactement la réponse qu'attend `retain` :

### Performance : - **Temps** : O(n) (cas moyen, en supposant une bonne distribution de hachage). - **Espace** : O(n) (pour le HashSet). ## 2. Tri + Dedup (détruit l'ordre) ### Étapes : 1. Trier le Vec (regroupe les doublons). 2. Supprimer les doublons consécutifs avec dedup(). ### Code : ```rust fn dedup_unordered(vec: &mut Vec) { vec.sort(); // O(n log n) vec.dedup(); // O(n) } ``` ### Exemple : ```rust let mut vec = vec![3, 2, 2, 1, 3]; dedup_unordered(&mut vec); assert_eq!(vec, [1, 2, 3]); // Ordre modifié ``` ### Performance : - **Temps** : O(n log n) (dominé par le tri). - **Espace** : O(1) (en place, pas d'allocations supplémentaires). ## Comparaison | Méthode | Complexité temporelle | Complexité spatiale | Préserve l'ordre ? | Cas d'usage | |--------|-----------------|------------------|------------------|----------| | HashSet | O(n) | O(n) | ✅ Oui | L'ordre est important, tri non autorisé. | | Tri + Dedup | O(n log n) | O(1) | ❌ Non | L'ordre est sans importance, mémoire limitée. | ## Choisir une stratégie de déduplication **Utilise HashSet si** : - L'ordre doit être préservé. - Tu peux tolérer un espace O(n). **Utilise Tri + Dedup si** : - L'ordre n'a pas d'importance. - La mémoire est limitée (ex : systèmes embarqués). ## Alternatives : - Pour les environnements no_std, utilise un BTreeSet (plus lent mais évite le hachage). - Utilise itertools::unique pour la déduplication basée sur les iterators. Quand `T` est `Clone` mais pas `Hash`, la voie du `HashSet` est fermée. `Vec::dedup_by` avec ton propre test d'égalité marche encore, à condition de trier l'entrée d'abord.