is it possible to filter on a vector in-place?

Question

I'd like to remove some elements from a Vec, but vec.iter().filter().collect() creates a new vector with borrowed items.

I'd like to mutate the original Vec without extra memory allocation (and keep memory of removed elements as an extra capacity of the vector).

Answer 1

If you truly want to mutate the vector's elements while filtering it, you can use the nightly-only method Vec::drain_filter, an extremely flexible tool:

#![feature(drain_filter)]

fn main() {
    let mut vec = vec![1, 2, 3, 4];
    vec.drain_filter(|x| {
        if *x % 2 == 0 {
            true
        } else {
            *x += 100;
            false
        }
    });
    assert_eq!(vec, [101, 103]);
}

It also allows you to get the removed elements as the return value of the entire method is an iterator!

Answer 2

I am providing my take for this problem as I was unaware of the retain method:

impl<T> RemoveFilter<T> for Vec<T> {}
pub trait RemoveFilter<T>: BorrowMut<Vec<T>> {
    fn remove_filter<F: for<'b> FnMut(&'b T) -> bool>(&mut self, mut cb: F) {
        let vec: &mut Vec<T> = self.borrow_mut();
        let mut write_to = 0;
        let mut read_from = 0;
        while read_from < vec.len() {
            let maintain = cb(&mut vec[read_from]);
            if maintain {
                vec.as_mut_slice().swap(read_from, write_to);
                write_to += 1;
            }
            read_from += 1;
        }
        vec.resize_with(write_to, || panic!("We are shrinking the vector"));
    }
}

It will shift the elements as it iterates and then remove anything that is left behind. I think this is code may easily modified to solve other problems.