Supprimer une séquence de valeurs d'un Vec en Rust ?

Question

remove sur un Vec supprime une seule valeur, donnée par un index, et renvoie cette valeur.

Je veux remove une liste d'indices, par exemple supprimer les indices 1, 2 et 5 d'une Vec de longueur 8, et obtenir les valeurs à ces indices comme un autre Vec . Appeler remove de manière répétée est (a) coûteux, et (b) sujet à erreur, car après chaque remove les autres indices sont déplacés.

Donc, si je commence avec let mut v = vec![2,3,4,5,6,7] et supprimé les indices [1,2,5] je me retrouverais avec un nouveau vecteur contenant vec![3,4,7] alors que v serait vec![2,5,6] .

Answer 1

Si les indices que vous souhaitez supprimer sont contigus, vous pouvez utiliser la commande Vec::drain comme indiqué dans cette réponse . Si ce n'est pas le cas (c'est-à-dire si vous avez des indices arbitraires que vous voulez supprimer), les choses deviennent beaucoup plus compliquées.

On peut résoudre le problème "coûteux" de remove en utilisant swap_remove . Au lieu de déplacer tous les éléments vers la gauche, il échangera l'élément retiré avec le dernier, ce qui constitue une opération O(1). Cependant, cela reste très sujet à erreur car les indices des éléments changent après chaque opération de suppression. De plus, l'ordre des éléments n'est pas le même que précédemment, ce qui peut ne pas vous convenir.

La seule façon (à laquelle je pense) de supprimer efficacement de multiples indices arbitraires est de trier ces indices par ordre décroissant .

/// `indices_to_remove` have to be sorted in decreased order!
fn remove_multiple<T>(source: &mut Vec<T>, indices_to_remove: &[usize]) -> Vec<T> {
    indices_to_remove.iter()
        .copied()
        .map(|i| source.swap_remove(i))
        .collect()
}

Exemple ( Terrain de jeux ) :

let mut vec = vec!['a', 'b', 'c', 'd', 'e', 'f'];
let removed = remove_multiple(&mut vec, &[5, 3, 2, 0]);
println!("source: {:?}", vec);        // ['e', 'b']
println!("result: {:?}", removed);    // ['f', 'd', 'c', 'a']

Si votre liste d'indices n'est pas triée, je pense en fait que le simple fait de la trier est le moyen le plus efficace d'atteindre votre objectif. Du moins, je ne vois pas d'algorithme qui garde la trace de tous les indices et qui soit plus rapide que O(n * log n), qui est le temps d'exécution du tri en premier.

Answer 2

Je viens de résoudre ce problème pour ma propre application, je vais donc partager le module. Il n'est pas parfait et je suis sûr qu'il peut être optimisé, mais il fonctionne suffisamment bien pour moi.

take_multiple() o take_multiple_in_order() fera exactement ce que vous vouliez dans la question originale.

pub trait RemoveMultiple<T> {
    /// Remove multiple indices
    fn remove_multiple(&mut self, to_remove: Vec<usize>);

    /// Remove multiple indices with swap_remove, this is faster but reorders elements
    fn swap_remove_multiple(&mut self, to_remove: Vec<usize>);

    /// Remove and return multiple indices
    fn take_multiple(&mut self, to_remove: Vec<usize>) -> Vec<T>;

    /// Remove and return multiple indices, preserving the order specified in the index list
    fn take_multiple_in_order(&mut self, to_remove: &[usize]) -> Vec<T>;

    /// Remove and return multiple indices with swap_remove, this is faster but reorders elements and the results are in reverse order
    fn swap_take_multiple(&mut self, to_remove: Vec<usize>) -> Vec<T>;
}

impl<T> RemoveMultiple<T> for Vec<T> {
    fn remove_multiple(&mut self, mut to_remove: Vec<usize>) {
        to_remove.sort();
        to_remove.reverse();
        for r in to_remove {
            self.remove(r);
        }
    }

    fn swap_remove_multiple(&mut self, mut to_remove: Vec<usize>) {
        to_remove.sort();
        to_remove.reverse();
        for r in to_remove {
            self.swap_remove(r);
        }
    }

    fn take_multiple(&mut self, mut to_remove: Vec<usize>) -> Vec<T> {
        to_remove.sort();
        to_remove.reverse();
        let mut collected = vec![];
        for r in to_remove {
            collected.push(self.remove(r));
        }
        collected.reverse();
        collected
    }

    fn take_multiple_in_order(&mut self, to_remove: &[usize]) -> Vec<T> {
        let mut to_remove = to_remove.iter().copied().enumerate().collect::<Vec<_>>();
        to_remove.sort_by_key(|(_, r)| *r);
        to_remove.reverse();
        let mut collected : Vec<Option<T>> = std::iter::repeat_with(|| None).take(to_remove.len()).collect();
        for (i, r) in to_remove {
            collected[i] = Some(self.remove(r));
        }
        collected.into_iter().filter_map(|x| x).collect()
    }

    fn swap_take_multiple(&mut self, mut to_remove: Vec<usize>) -> Vec<T> {
        to_remove.sort();
        to_remove.reverse();
        let mut collected = vec![];
        for r in to_remove {
            collected.push(self.swap_remove(r));
        }
        collected
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn remove_multiple() {
        let mut list = vec!['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];        
        list.remove_multiple(vec![8, 0, 5, 6]);
        assert_eq!(vec!['1', '2', '3', '4','7', '9'], list);             
    }

    #[test]
    fn swap_remove_multiple() {
        let mut list = vec!['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];        
        list.swap_remove_multiple(vec![8, 0, 5, 6]);
        assert_eq!(vec!['9', '1', '2', '3', '4', '7'], list);      
    }

    #[test]
    fn take_multiple() {
        let mut list = vec!['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];        
        let taken = list.take_multiple(vec![8, 0, 5, 6]);
        assert_eq!(vec!['1', '2', '3', '4','7', '9'], list); 
        assert_eq!(vec!['0', '5', '6', '8'], taken);             
    }

    #[test]
    fn swap_take_multiple() {
        let mut list = vec!['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];        
        let taken = list.swap_take_multiple(vec![8, 0, 5, 6]);
        assert_eq!(vec!['9', '1', '2', '3', '4', '7'], list); 
        assert_eq!(vec!['8', '6', '5', '0'], taken);                
    }

    #[test]
    fn take_multiple_in_order() {
        let mut list = vec!['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];        
        let taken = list.take_multiple_in_order(&vec![8, 0, 5, 6]);
        assert_eq!(vec!['1', '2', '3', '4','7', '9'], list); 
        assert_eq!(vec!['8', '0', '5', '6'], taken);             
    }
}