问题描述
我正在尝试在 Rust 中实现惰性构造/记忆化评估/缓存习语.
I'm trying to implement a lazy-construction / memoized evaluation / caching idiom in Rust.
有一个外部类型,它有一堆数据和一个访问器方法.访问器方法需要返回一个缓存的计算(如果有的话)或者计算它并将返回值存储在映射中以供以后使用.缓存值不需要引用外部值,所以不存在循环引用问题;但它确实需要访问外部值的数据才能构建自己.
There's an outer type which has a bunch of data and an accessor method. The accessor method needs to either return a cached calculation (if it has one) or calculate it and store the return value in a map for later use. The cached value doesn't need to reference the outer value so there's no circular reference problem; but it does need access to the outer value's data in order to construct itself.
这是一个没有通过 Rust 借用检查器的完整示例:
Here's a full example which doesn't pass Rust's borrow checker:
use std::collections::HashMap;
pub struct ContainedThing {
count: usize,
}
impl ContainedThing {
fn create(thing: &Thing) -> ContainedThing {
// create uses an arbitrary number of attributes from Thing
// it doesn't keep any references after returning though
let count = thing.map.len();
ContainedThing { count: count }
}
}
struct Thing {
map: HashMap<i32, ContainedThing>,
}
impl Thing {
pub fn get(&mut self, key: i32) -> &ContainedThing {
self.map
.entry(key)
.or_insert_with(|| ContainedThing::create(&self))
}
}
fn main() {}
具体错误是:
error[E0502]: cannot borrow `self` as immutable because `self.map` is also borrowed as mutable
--> src/main.rs:24:29
|
22 | self.map
| -------- mutable borrow occurs here
23 | .entry(key)
24 | .or_insert_with(|| ContainedThing::create(&self))
| ^^ ---- borrow occurs due to use of `self` in closure
| |
| immutable borrow occurs here
25 | }
| - mutable borrow ends here
我很难找到实现这个成语的好方法.我尝试了模式匹配 get()
而不是 entry()
API 的返回值,但仍然遇到借用检查器:match
表达式最终也会借用 self
.
I'm having a really hard time figuring out a good way to implement this idiom. I tried pattern matching the return value of get()
instead of the entry()
API, but still fell foul of the borrow checker: the match
expression also ends up borrowing self
.
我可以像这样重写 get
:
pub fn get(&mut self, key: i32) -> &ContainedThing {
if !self.map.contains_key(&key) {
let thing = ContainedThing::create(&self);
self.map.insert(key, thing);
}
self.map.get(&key).unwrap()
}
但这很丑(看看那个unwrap
),而且似乎需要更多的查找和复制.理想情况下,我愿意
but this is pretty ugly (look at that unwrap
) and seems to require more lookups and copies than ought to be necessary. Ideally, I would like
- 只需支付一次查找哈希条目的费用.
entry()
,做对了,应该在没有找到的时候跟踪插入位置. - 减少新构造值的副本数.这可能是不可行的,理想情况下我会有一个就地构造.
- 避免使用
unwrap
;没有毫无意义的模式匹配,也就是说.
- to only pay the cost of finding the hash entry once.
entry()
, done right, ought to track the insertion location when not found. - reduce the number of copies of the freshly constructed value. This may be infeasible, ideally I'd have an in-place construction.
- to avoid using
unwrap
; without a pointless pattern match, that is.
我笨拙的代码是可以实现的最好的吗?
Is my clumsy code the best that can be achieved?
推荐答案
答案是具体取决于您需要在 or_insert_with
闭包中访问哪个状态.问题是 or_insert_with
绝对不能访问地图本身,因为入口 api 需要可变借用地图.
The answer is that it depends on specifically which state you need access to in the or_insert_with
closure. The problem is that or_insert_with
definitely cannot have access to the map itself because the entry api takes a mutable borrow of the map.
如果 ContainedThing::create
只需要地图的大小,那么您只需提前计算地图的大小.
If all you need for ContainedThing::create
is just the size of the map, then you'll just need to calculate the map size ahead of time.
impl Thing {
pub fn get(&mut self, key: i32) -> &ContainedThing {
let map_size = self.map.len();
self.map.entry(&key).or_insert_with(|| {
// The call to entry takes a mutable reference to the map,
// so you cannot borrow map again in here
ContainedThing::create(map_size)
})
}
}
不过,我认为这个问题的精神更多地是关于一般策略,所以我们假设 Thing
中还有一些其他状态也是创建 ContainedThing
所必需的.
I think the spirit of the question was more about general strategies, though, so let's assume there's some other state within Thing
that is also required to create ContainedThing
.
struct Thing {
map: HashMap<i32, ContainedThing>,
some_other_stuff: AnotherType, //assume that this other state is also required in order to create ContainedThing
}
impl Thing {
pub fn get(&mut self, key: i32) -> &ContainedThing {
//this is the borrow of self
let Thing {
ref mut map,
ref mut some_other_stuff,
} = *self;
let map_size = map.len();
map.entry(key).or_insert_with(|| {
// map.entry now only borrows map instead of self
// Here you're free to borrow any other members of Thing apart from map
ContainedThing::create(map_size, some_other_stuff)
})
}
}
这是否真的比您手动检查 if self.map.contains_key(&key)
的其他解决方案更清洁有待商榷.不过,解构往往是我采用的策略,它允许借用 self
的特定成员而不是整个结构.
Whether that's really cleaner than your other solution of manually checking if self.map.contains_key(&key)
is up for debate. Destructuring tends to be the strategy that I go for, though, to allow borrowing specific members of self
instead of the entire struct.
这篇关于如何在 Rust 中懒惰地创建其构造使用 self 的地图条目的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!