vector - 我应该如何存储要从中删除但从不添加的项目列表？

Question

我正在实现一个函数，在该函数中，我将重复地从一个大列表中消除值，并在每次迭代时将此列表的副本作为向量传递到另一个函数中:

let mut v = vec![5, 4, 4, 2, 6, 5, 1, 8, 2, 1, 6, 5, 4, 2, 0, 1];
for i in 0..10 {
    println!("{}", Vector::from(v).iter().sum());
    v.retain(|x| x > i);
}

如果v非常大，这会很慢。有没有更好的办法？我尝试过:

let mut v = vec![5, 4, 4, 2, 6, 5, 1, 8, 2, 1, 6, 5, 4, 2, 0, 1];
let mut v = v.into_iter().map(|x| Some(x)).collect();

(然后用 None 替换“已删除”值)，但这似乎难以在普通的 Vec 之间进行转换。

我应该如何存储这个值列表？

Answer 1

您可以重组复制列表的创建，以便在复制之前进行删除:

for i in 0..10 {
    let dup = your_list.iter().filter(|n| n > i).collect::<Vec<_>>();
    use_it(dup);
}

如果对于您的用例来说，留下过滤后的 Vec 很重要，并且无法更改集合类型，那么这可能是最有用的方法。如果过滤器是累积的，您可以在每次迭代时用过滤后的Vec覆盖原始Vec，以减少以后每次迭代的工作量。

let mut list = your_list;
for i in 0..10 {
    list = list.iter().filter(|n| n > i).collect();
    use_it(list.clone());
}

---

您提出的问题可以通过 reshape 过滤和复制向量的方式来直接回答，但如果您能够更改类型，那么下面的答案可能更有值(value)。

如果您的 use_it 函数不需要 Vec 或切片，那么通过重构消费者以采用迭代器可能会更好。数字，并传入 your_list.iter().filter(...)。这将导致内存中不会进行复制或重新排列，并且消费者函数将仅跳过无效值。

如果您更关心计算数字在集合中出现的次数，并且不需要内存中的顺序列表，则可以将列表重新排列为 HashMap:

use std::collections::HashMap;
let mut dict: HashMap<i32, usize> = HashMap::new();
for num in your_list {
    *dict.entry(num).or_insert(0) += 1;
}

然后您可以通过恒定时间访问(而不是集合大小的线性时间)从 map 中过滤出数字。