从通过迭代找到的 BTreeMap 或 BTreeSet 中删除项目 [英] Removing items from a BTreeMap or BTreeSet found through iteration
问题描述
我想从通过迭代找到的 BTreeMap 中删除项目.
I would like to remove items from a BTreeMap which have been found through iteration.
由于迭代时无法删除项目，我将要删除的项目放入向量中.主要问题是不可能使用引用的向量，而只能使用值的向量.然后必须克隆所有必须删除条目的键(假设该键实现了 Clone trait).
As it is not possible to remove items while iterating, I put the items to delete into a vector. The main issue is that it is not possible to use a vector of references, but only a vector of values. All the keys for which the entry has to be removed must then be cloned (assuming the key implements the Clone trait).
例如，这个简短的示例无法编译:
For instance, this short sample does not compile:
use std::collections::BTreeMap;
pub fn clean() {
let mut map = BTreeMap::<String, i32>::new();
let mut to_delete = Vec::new();
{
for (k, v) in map.iter() {
if *v > 10 {
to_delete.push(k);
}
}
}
for k in to_delete.drain(..) {
map.remove(k);
}
}
fn main() {}
它在编译时产生以下错误:
It generates the following errors when it is compiled:
error[E0502]: cannot borrow `map` as mutable because it is also borrowed as immutable
--> src/main.rs:17:9
|
9 | for (k, v) in map.iter() {
| --- immutable borrow occurs here
...
17 | map.remove(k);
| ^^^ mutable borrow occurs here
18 | }
19 | }
| - immutable borrow ends here
使用 to_delete.push(k.clone()) 更改 to_delete.push(k) 可以使此代码段正确编译，但如果要删除每个键，则成本会很高必须克隆.
Changing to_delete.push(k) with to_delete.push(k.clone()) makes this snippet compile correctly but it is quite costly if each key to delete must be cloned.
有更好的解决方案吗?
推荐答案
TL;DR:你不能.
就编译器而言，BTreeMap::remove 可能会这样做:
As far as the compiler is concerned, the implementation of BTreeMap::remove might do this:
pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
// actual deleting code, which destroys the value in the set
// now what `value` pointed to is gone and `value` points to invalid memory
// And now we access that memory, causing undefined behavior
key.borrow();
}
因此，当集合发生变异时，编译器必须防止使用对值的引用.
The compiler thus has to prevent using the reference to the value when the collection will be mutated.
要做到这一点，您需要类似于集合的假设光标"API.这将允许您遍历集合，返回一个特殊类型，该类型保存集合的可变内部.这种类型可以为您提供一个参考以进行检查，然后允许您删除该项目.
To do this, you'd need something like the hypothetical "cursor" API for collections. This would allow you to iterate over the collection, returning a special type that hold the mutable innards of the collection. This type could give you a reference to check against and then allow you to remove the item.
我可能会从稍微不同的方向看问题.我不想保留地图，而是创建一个全新的地图:
I'd probably look at the problem from a bit different direction. Instead of trying to keep the map, I'd just create a brand new one:
use std::collections::BTreeMap;
pub fn main() {
let mut map = BTreeMap::new();
map.insert("thief", 5);
map.insert("troll", 52);
map.insert("gnome", 7);
let map: BTreeMap<_, _> =
map.into_iter()
.filter(|&(_, v)| v <= 10)
.collect();
println!("{:?}", map); // troll is gone
}
<小时>
如果您的条件在使结构唯一的字段上相等(也就是在PartialEq 和Hash 中使用的唯一字段)，你可以为你的类型实现 Borrow 并直接抓取它/删除它:
If your condition is equality on the field that makes the struct unique (a.k.a is the only field used in PartialEq and Hash), you can implement Borrow for your type and directly grab it / delete it:
use std::collections::BTreeMap;
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Monster(String);
use std::borrow::Borrow;
impl Borrow<str> for Monster {
fn borrow(&self) -> &str { &self.0 }
}
pub fn main() {
let mut map = BTreeMap::new();
map.insert(Monster("thief".into()), 5);
map.insert(Monster("troll".into()), 52);
map.insert(Monster("gnome".into()), 7);
map.remove("troll");
println!("{:?}", map); // troll is gone
}
另见:
这篇关于从通过迭代找到的 BTreeMap 或 BTreeSet 中删除项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
