如何根据元素从向量中删除一个元素？

Question

有没有一种简单的方法可以从 Vec<T> 中删除元素？

有一个名为 remove() 的方法，它需要一个 index: usize，但我甚至看不到一个 index_of() 方法。

我正在寻找一些（希望）简单的且 O(n) 的东西。

- Kai Sellgren

Answer 1

这是我目前想出来的（也让借用检查器满意）：

let index = xs.iter().position(|x| *x == some_x).unwrap();
xs.remove(index);

我仍在等待找到更好的方法来做这件事，因为它很丑陋。

注意：我的代码假设该元素存在（因此使用了.unwrap()）。

- Kai Sellgren

---

请注意：标准库仍在设计中，因此可能缺少其他语言中常见的一些函数。欢迎您提交 PR 来添加它们！ - aochagavia

使用 Rust 一段时间后，通常会在索引列表中进行删除操作，因此在索引上进行过滤/保留实际上比从中间删除要便宜得多。 - Kamil Tomšík

Rust实际上曾经有一个完全可以做到这一点的函数，但后来将其弃用https://doc.rust-lang.org/std/vec/struct.Vec.html#method.remove_item，所以我想他们只是认为它不必要。 - EarthenSky

Answer 2

您可以使用retain方法，但它会删除每个值的所有实例：

fn main() {
    let mut xs = vec![1, 2, 3];
    let some_x = 2;
    xs.retain(|&x| x != some_x);
    println!("{:?}", xs); // prints [1, 3]
}

- antoyo

---

找到元素后进行的比较是不必要的。 - malbarbo

@malbarbo 是的，这是因为该方法会删除所有值的实例。 - antoyo

Answer 3

你的问题没有明确说明：你是想返回所有等于needle的项目还是只返回一个？ 如果是一个，是第一个还是最后一个？如果没有单个元素等于你的needle会怎样？能否使用快速的swap_remove删除它，还是需要使用较慢的remove？为了强迫程序员思考这些问题，没有简单的方法可以“删除一个项目”（有关更多信息，请参见此讨论）。

删除第一个等于needle的元素

// Panic if no such element is found
vec.remove(vec.iter().position(|x| *x == needle).expect("needle not found"));

// Ignore if no such element is found
if let Some(pos) = vec.iter().position(|x| *x == needle) {
    vec.remove(pos);
}

当然，你可以按照自己的意愿处理None情况（恐慌和忽略不是唯一的可能性）。

删除等于needle的最后一个元素

与第一个元素相似，但用rposition替换position。

删除所有等于needle的元素

vec.retain(|x| *x != needle);

...或者使用swap_remove

请记住，remove的运行时间复杂度为O(n)，因为需要对索引后面的所有元素进行移动。而Vec::swap_remove的运行时间复杂度为O(1)，因为它将要删除的元素与最后一个元素交换位置。如果在您的情况下元素的顺序不重要，请使用swap_remove而不是remove!

- Lukas Kalbertodt

Answer 4

迭代器有一个position()方法，可返回第一个匹配断言的元素的索引。相关问题：是否有 Rust 数组等价于 JavaScript 的 indexOf 方法？

代码示例：

fn main() {
    let mut vec = vec![1, 2, 3, 4];

    println!("Before: {:?}", vec);

    let removed = vec.iter()
        .position(|&n| n > 2)
        .map(|e| vec.remove(e))
        .is_some();

    println!("Did we remove anything? {}", removed);

    println!("After: {:?}", vec);
}

- A.B.

---

这段代码无法编译：xs.remove(xs.iter().position(|x| *x == some_x).unwrap()); -- "无法将 xs 借为不可变的，因为它同时也被作为可变的借用了"。 - Kai Sellgren

也被称为：不要修改你正在迭代的容器。 - Matthieu M.

Answer 5

drain_filter()方法是否是最新的？

看起来与Kai的答案相似：

#![feature(drain_filter)]
let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];

numbers.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();

assert_eq!(numbers, vec![1, 3, 5, 9, 11, 13, 15]);

https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain_filter

- Mikeumus

---

drain_filter：仍然只适用于夜间版本和实验性质。 - Wolfgang Kuehn

一年多过去了，@WolfgangKuehn仍然是实验性的。:-P - Markus

只有在需要移除的元素时（在这种情况下你不需要访问它们），才使用extract_if()。否则，请使用retain()。另外，为什么要使用.collect::<Vec<_>>()？ - undefined

Answer 6

如果您的数据已排序，请使用二分查找进行 O(log n) 的删除操作，这对于大输入数据能够更快地完成。

match values.binary_search(value) {
  Ok(removal_index) => values.remove(removal_index),
  Err(_) => {} // value not contained.
}

- Will Brickner

---

无论如何，删除操作都是O(log n)，因此即使其搜索部分是O(log n)，但该解决方案并非O(log n)。 - avl_sweden

在99%的实际情况下，您想要的数据结构是HashSet。然后搜索和删除的时间复杂度为O(1)。 - avl_sweden

他只是建议如果所有设置都可以的话，将顺序搜索部分更改为二进制搜索，这是一个有效的关注点。所以只是试图帮助，不应该被评为-1。 - rsalmei

Answer 7

由于没有人提供这个解决方案：

pub trait RemoveElem<T> {
    fn remove_elem<F>(&mut self, predicate: F) -> Option<T>
    where
        F: Fn(&T) -> bool;
}

impl<T> RemoveElem<T> for Vec<T> {
    fn remove_elem<F>(&mut self, predicate: F) -> Option<T>
    where
        F: Fn(&T) -> bool,
    {
        self.iter()
            .position(predicate)
            .map(|index| self.remove(index))
    }
}

像这样，我们可以直接在向量上调用函数：

let mut a1 = vec![1, 2, 1];
a1.remove_elem(|e| e == &1);
dbg!(&a1); // ouput: [ 2, 1 ]

- wiiznokes3