是否可以就地过滤向量？

Question

我想从

Vec

中删除一些元素，但是

vec.iter().filter().collect()

使用借来的项目创建一个新向量。

我想在没有额外内存分配的情况下改变原始

Vec

（并将删除元素的内存保留为向量的额外容量）。

Answer 1

如果要删除元素，可以使用

retain()

，如果闭包返回

false

，它会从向量中删除元素：

let mut vec = vec![1, 2, 3, 4];
vec.retain(|&x| x % 2 == 0);
assert_eq!(vec, [2, 4]);

如果你想修改元素，你必须在

for x in vec.iter_mut()

中进行。

Answer 2

如果您确实想在过滤向量的同时改变向量的元素，您可以使用仅限夜间的方法Vec::extract_if

，这是一个非常灵活的工具：

#![feature(extract_if)]

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

它还允许您获取删除的元素，因为整个方法的返回值是一个迭代器！

for_each(drop)

是必需的，否则

extract_if()

将不起作用。在现实生活中，如果您不需要返回的元素，请使用 

retain()

，如 @eulerdisk 的答案。

Answer 3

直到

Vec::extract_if

稳定下来，我们就可以用自制的锈解决问题了：

fn main() {
    let mut v = vec![1, 2, 3, 4];
    let mut i = 0;
    while i < v.len() {
        if v[i] % 2 == 0 {
            v.remove(i);
        } else {
            v[i] += 100;
            i += 1;
        }
    }
    println!("{:?}", v);  // [101, 103]
}

顺便说一句，

remove()

是一个

O(n)

操作，但不分配内存。

游乐场

Answer 4

我提供了我对这个问题的看法，因为我不知道保留方法：

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"));
    }
}

它将在迭代时移动元素，然后删除留下的任何内容。我认为这个代码可以很容易地修改来解决其他问题。