Removing multiple indices from a vector

help
1 
vector = [0, 1, 2, 3, 4]
vector.remove(1)
vector.remove(3)

// Intended output
// vector == [0, 2, 4]

// Actual output
assert_eq!(vector, [0, 2, 3]

I have an array of IDs and I want the user to be able to select which ones they want to delete. I used dialoguer::MultiSelect for this. It returns a vector of indices of the elements selected. But as shown in the example above, removing multiple elements using their indices isn't that straight forward. I searched online but I couldn't find anything about this (for Rust at least). My only solution so far is to put the contents of these indices in another vector (say vec_buf) and then iterate through each element in vec_buf, removing the element from vector using their content. But this is a terrible solution so does anyone have a more idiomatic solution?

Edit:
I've just thought of another solution which is to mirror the vector to a hashmap with the indices as keys. Then the indices will not change when removing elements

2

If you remove them in reverse order then you won't have to deal with shifting indices.

Removing an item from a vector is O(n) though. If you remove a large number of indices then you're going to be dealing with O(n2) performance. That may be negligible if the vector is small. If it's large, though, I recommend writing a manual loop where you remove and shift items in a single pass (without calling .remove).

Or yeah, go with the hash map.

2 Likes
3

For my program's use case, there is realistically never gonna be any more than 100-150 elements in the vector and removing items is probably not going to be more than 10 at once so yeah I'm not too concerned about performance.

4

You don't even need a hash map for it. You can just copy to another vector. If you know the indices are sorted in increasing order, you can merge-sort your way through the problem: Playground.

fn remove_sorted_indices<T>(v: impl IntoIterator<Item=T>, indices: impl IntoIterator<Item=usize>) -> Vec<T> {
    let v = v.into_iter();
    let mut indices = indices.into_iter();
    let mut i = match indices.next() {
        None => return v.collect(),
        Some(i) => i,
    };
    let (min, max) = v.size_hint();
    let mut result = Vec::with_capacity(max.unwrap_or(min));
    
    for (j, x) in v.into_iter().enumerate() {
        if j == i {
            if let Some(idx) = indices.next() {
                i = idx;
            }
        } else {
            result.push(x);
        }
    }
    
    result
}

fn main() {
    let v = vec!["0", "1", "2", "3", "4", "5", "6", "7"];
    let r = remove_sorted_indices(v, [0, 2, 5]);
    println!("{:?}", r);
}
5

Do you need to preserve the order of the non-removed items?

Vec::swap_remove is in-place and O(1).

2 Likes
6

You could do this with Vec::retain -- it's documented to visit things in order, so you can use mutable state in the closure to keep track of which item index you're on, and say to keep it only if it's not in your other list of indices.

6 Likes
7

Maybe use a vec of Options and when you get the list of indices set those slots to None. Then you can pack the vec removing the None's.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.