Rust Book 第 13.1 章，用泛型参数包装 HashMap
Rust Book chapter 13.1, wrapping a HashMap with generic parameters
我已经用 HashMap<u32, u32> 成功地实现了 Cacher，我想按照书中的建议用完全通用的类型来实现它。目前我的代码看起来像这样，但它没有编译，我没有想法。编译错误与在 value() 方法中移动 v 有关，如果我将整个代码更改为接受 &u32 而不是 u32，问题仍然存在。
use std::{thread, time::Duration, collections::HashMap, hash::Hash};
struct Cacher<T, K, V>
where
T: Fn(K) -> V,
K: Eq + Hash
{
calculation: T,
values: HashMap<K, V>,
}
impl<T, K, V> Cacher<T, K, V>
where
T: Fn(K) -> V,
K: Eq + Hash
{
fn new(calculation: T) -> Self {
Cacher {
calculation,
values: HashMap::new(),
}
}
fn value(&mut self, arg: K) -> V {
if let Some(v) = self.values.get(&arg) {
*v
} else {
let v = (self.calculation)(arg);
self.values.insert(arg, v);
v
}
}
}
// rest of the code
fn main() {
let simulated_user_specified_value = 10;
let simulated_random_number = 7;
generate_workout(simulated_user_specified_value, simulated_random_number);
}
fn generate_workout(intensity: u32, random_number: u32) {
let mut expensive_closure: Cacher<_, u32, u32> = Cacher::new(|num: u32| {
println!("calculating slowly...");
thread::sleep(Duration::from_secs(2));
num
});
if intensity < 25 {
println!("Today do {} pushups!", expensive_closure.value(intensity));
println!("Next, do {} situps!", expensive_closure.value(intensity));
} else {
if random_number == 3 {
println!("Take a break today! Remember to stay hydrated!");
} else {
println!("Today run for {} minutes!", expensive_closure.value(intensity));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn call_with_different_values() {
let mut c = Cacher::new(|a| a);
let v1 = c.value(1);
let v2 = c.value(2);
assert_eq!(v1, 1);
assert_eq!(v2, 2);
}
}
编辑：修正了错误的代码的最终版本：
use std::{thread, time::Duration, collections::HashMap, hash::Hash};
struct Cacher<T, K, V>
where
T: Fn(&K) -> V,
K: Eq + Hash
{
calculation: T,
values: HashMap<K, V>,
}
impl<T, K, V> Cacher<T, K, V>
where
T: Fn(&K) -> V,
K: Eq + Hash
{
fn new(calculation: T) -> Self {
Cacher {
calculation,
values: HashMap::new(),
}
}
fn value(&mut self, arg: K) -> &V {
self.values.entry(arg).or_insert_with_key(&self.calculation)
}
}
// rest of the code
fn main() {
let simulated_user_specified_value = 10;
let simulated_random_number = 7;
generate_workout(simulated_user_specified_value, simulated_random_number);
}
fn generate_workout(intensity: u32, random_number: u32) {
let mut expensive_closure: Cacher<_, u32, u32> = Cacher::new(|num: &u32| {
println!("calculating slowly...");
thread::sleep(Duration::from_secs(2));
*num
});
if intensity < 25 {
println!("Today do {} pushups!", expensive_closure.value(intensity));
println!("Next, do {} situps!", expensive_closure.value(intensity));
} else {
if random_number == 3 {
println!("Take a break today! Remember to stay hydrated!");
} else {
println!("Today run for {} minutes!", expensive_closure.value(intensity));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn call_with_different_values() {
let mut c = Cacher::new(|a| *a);
let v1 = c.value(1);
assert_eq!(*v1, 1);
let v2 = c.value(2);
assert_eq!(*v2, 2);
}
}
在 Rust 中，默认情况下，对象是不可复制的。
假设我们要缓存 Vec<i32> 类型的值。在 Cacher::value() 中，我们取 arg: Vec<i32>。现在假设键已经在缓存映射中。我们可以获得对它的引用，但是如果我们想要 return 键入 V，就像现在一样，即 Vec<i32>，我们必须获得引用的拥有版本。现在假设如果执行 *v 的代码可以编译会发生什么。当调用者销毁（丢弃）该值时，Vec 的存储将被释放，我们将在缓存中释放一个 Vec！下次我们将查找相同的键时，我们将得到一个无效的 Vec，我们将尝试执行的任何操作都将是未定义的行为！这太可怕了，正是 Rust 旨在防止的那种错误。
钥匙也会发生类似的事情。假设我们的参数是 Vec<i32> 类型。当我们将它传递给位于 (self.calculation)(arg) 的计算器时，它将释放它，当我们尝试在下一行将其存储在缓存中时 (self.values.insert(arg, v))，我们将存储一个无效的 Vec!
有两种方法可以解决这个问题，正确的方法取决于您的问题的具体细节。
第一种方法就是不要让他们（消费者和计算器）破坏价值。也就是说，我们不会让他们改变这个值，只会检查它（技术上，我们可以让他们改变 而不是 destroy，但这会导致不同的问题）。或者，用 Rust 的术语来说，我们会给他们一个 reference 而不是 owned value。这将有一个明显的缺点，即他们将无法更改它：在某些情况下，他们可能需要这样做，然后第二个选项可能更可取。
尝试在代码中对其进行建模会给我们带来一些错误：
T: Fn(K) -> V,
// Replace with
T: Fn(&K) -> V,
// And
fn value(&mut self, arg: K) -> &V {
if let Some(v) = self.values.get(&arg) {
v
} else {
let v = (self.calculation)(&arg);
self.values.insert(arg, v);
&v
}
}
error[E0502]: cannot borrow `self.values` as mutable because it is also borrowed as immutable
--> src/lib.rs:29:13
|
24 | fn value(&mut self, arg: K) -> &V {
| - let's call the lifetime of this reference `'1`
25 | if let Some(v) = self.values.get(&arg) {
| --------------------- immutable borrow occurs here
26 | v
| - returning this value requires that `self.values` is borrowed for `'1`
...
29 | self.values.insert(arg, v);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
error[E0515]: cannot return reference to local variable `v`
--> src/lib.rs:30:13
|
30 | &v
| ^^ returns a reference to data owned by the current function
error[E0382]: borrow of moved value: `v`
--> src/lib.rs:30:13
|
28 | let v = (self.calculation)(&arg);
| - move occurs because `v` has type `V`, which does not implement the `Copy` trait
29 | self.values.insert(arg, v);
| - value moved here
30 | &v
| ^^ value borrowed here after move
这有点过分了！
第一个错误实际上是 Rust 借用检查器的当前限制：代码没有编译器认为存在的问题，但编译器无法证明这一点。 Future projects are going to help the compiler figure it, but in the meantime, there is something we can do: Rust's hashmap has a construct designed exactly for this situation of insert-if-not-already-there: the entry API. Using it, our code looks like (playground):
fn value(&mut self, arg: K) -> &V {
// `&self.calculation` is really equal here to `|arg| (self.calculation)(arg)`, just shorter.
self.values.entry(arg).or_insert_with_key(&self.calculation)
}
神奇的是，我们还解决了另外两个问题！很好，但为了知识起见，我仍然会解释问题所在。
我们将v移动到hashmap中，然后使用它。这就是问题。再次考虑 v 具有类型 Vec<i32> 的情况。如果我们可以使用它，我们需要在之后销毁它 - 但它在地图内部，我们无法销毁它！出于这个原因，编译器拒绝了我们的代码并出现第三个错误。
至于第二个错误，我们return参考了v。但是 v 是一个局部变量，在函数结束时被销毁 - 所以我们会 return 引用无效数据！
修复它们 non-trivial（甚至不可能），所以我不想在这里解释它。
第二种解决方法是首先思考“为什么它适用于 i32、non-generic 版本？
答案很简单：之所以有效，是因为“摧毁”i32 不会造成任何伤害。更正式地说，i32 不持有某些资源，如 Vec 持有分配：它只是普通数据，复制它 - 只是按位，简单的复制 - 总是没问题的。或者，用 Rust 术语来说，i32 实现了 Copy.
这就提出了一个问题：我们可以在通用版本中表达这个规则吗？即说“我们只想允许复制始终有效的类型，即 实现 Copy？”事实证明，答案是，是的！我们只需要添加一个 where Type: Copy 绑定 (playground):
where
T: Fn(K) -> V,
K: Eq + Hash + Copy,
V: Copy,
有一种方法可以概括这一点：目前，这只允许 按位复制 - 也就是说，只允许可以自由复制完全相同位模式的类型。但是我们也可以允许 custom-copy 代码，并且允许像 Vec 这样的东西，在持有资源的同时，可以通过分配新内存和复制内容来复制。该特征称为 Clone，但它要求我们在复制值时更明确一点（注意每个 Copy 也是 Clone，因此它也适用于类型如 i32):
where
T: Fn(K) -> V,
K: Eq + Hash + Clone,
V: Clone,
fn value(&mut self, arg: K) -> V {
if let Some(v) = self.values.get(&arg) {
v.clone()
} else {
let v = (self.calculation)(arg.clone());
self.values.insert(arg, v.clone());
v
}
}
如果您对选择哪个选项有疑问，或者您不知道代码的客户需要什么，请选择第一个选项。它更通用，因为它允许任何类型（不仅仅是那些实现 Clone 的类型），如果他们需要它，他们总是可以 .clone() 值然后改变它，即使这有点不方便.
我已经用 HashMap<u32, u32> 成功地实现了 Cacher，我想按照书中的建议用完全通用的类型来实现它。目前我的代码看起来像这样，但它没有编译，我没有想法。编译错误与在 value() 方法中移动 v 有关，如果我将整个代码更改为接受 &u32 而不是 u32，问题仍然存在。
use std::{thread, time::Duration, collections::HashMap, hash::Hash};
struct Cacher<T, K, V>
where
T: Fn(K) -> V,
K: Eq + Hash
{
calculation: T,
values: HashMap<K, V>,
}
impl<T, K, V> Cacher<T, K, V>
where
T: Fn(K) -> V,
K: Eq + Hash
{
fn new(calculation: T) -> Self {
Cacher {
calculation,
values: HashMap::new(),
}
}
fn value(&mut self, arg: K) -> V {
if let Some(v) = self.values.get(&arg) {
*v
} else {
let v = (self.calculation)(arg);
self.values.insert(arg, v);
v
}
}
}
// rest of the code
fn main() {
let simulated_user_specified_value = 10;
let simulated_random_number = 7;
generate_workout(simulated_user_specified_value, simulated_random_number);
}
fn generate_workout(intensity: u32, random_number: u32) {
let mut expensive_closure: Cacher<_, u32, u32> = Cacher::new(|num: u32| {
println!("calculating slowly...");
thread::sleep(Duration::from_secs(2));
num
});
if intensity < 25 {
println!("Today do {} pushups!", expensive_closure.value(intensity));
println!("Next, do {} situps!", expensive_closure.value(intensity));
} else {
if random_number == 3 {
println!("Take a break today! Remember to stay hydrated!");
} else {
println!("Today run for {} minutes!", expensive_closure.value(intensity));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn call_with_different_values() {
let mut c = Cacher::new(|a| a);
let v1 = c.value(1);
let v2 = c.value(2);
assert_eq!(v1, 1);
assert_eq!(v2, 2);
}
}
编辑：修正了错误的代码的最终版本：
use std::{thread, time::Duration, collections::HashMap, hash::Hash};
struct Cacher<T, K, V>
where
T: Fn(&K) -> V,
K: Eq + Hash
{
calculation: T,
values: HashMap<K, V>,
}
impl<T, K, V> Cacher<T, K, V>
where
T: Fn(&K) -> V,
K: Eq + Hash
{
fn new(calculation: T) -> Self {
Cacher {
calculation,
values: HashMap::new(),
}
}
fn value(&mut self, arg: K) -> &V {
self.values.entry(arg).or_insert_with_key(&self.calculation)
}
}
// rest of the code
fn main() {
let simulated_user_specified_value = 10;
let simulated_random_number = 7;
generate_workout(simulated_user_specified_value, simulated_random_number);
}
fn generate_workout(intensity: u32, random_number: u32) {
let mut expensive_closure: Cacher<_, u32, u32> = Cacher::new(|num: &u32| {
println!("calculating slowly...");
thread::sleep(Duration::from_secs(2));
*num
});
if intensity < 25 {
println!("Today do {} pushups!", expensive_closure.value(intensity));
println!("Next, do {} situps!", expensive_closure.value(intensity));
} else {
if random_number == 3 {
println!("Take a break today! Remember to stay hydrated!");
} else {
println!("Today run for {} minutes!", expensive_closure.value(intensity));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn call_with_different_values() {
let mut c = Cacher::new(|a| *a);
let v1 = c.value(1);
assert_eq!(*v1, 1);
let v2 = c.value(2);
assert_eq!(*v2, 2);
}
}
在 Rust 中，默认情况下，对象是不可复制的。
假设我们要缓存 Vec<i32> 类型的值。在 Cacher::value() 中，我们取 arg: Vec<i32>。现在假设键已经在缓存映射中。我们可以获得对它的引用，但是如果我们想要 return 键入 V，就像现在一样，即 Vec<i32>，我们必须获得引用的拥有版本。现在假设如果执行 *v 的代码可以编译会发生什么。当调用者销毁（丢弃）该值时，Vec 的存储将被释放，我们将在缓存中释放一个 Vec！下次我们将查找相同的键时，我们将得到一个无效的 Vec，我们将尝试执行的任何操作都将是未定义的行为！这太可怕了，正是 Rust 旨在防止的那种错误。
钥匙也会发生类似的事情。假设我们的参数是 Vec<i32> 类型。当我们将它传递给位于 (self.calculation)(arg) 的计算器时，它将释放它，当我们尝试在下一行将其存储在缓存中时 (self.values.insert(arg, v))，我们将存储一个无效的 Vec!
有两种方法可以解决这个问题，正确的方法取决于您的问题的具体细节。
第一种方法就是不要让他们（消费者和计算器）破坏价值。也就是说，我们不会让他们改变这个值，只会检查它（技术上，我们可以让他们改变 而不是 destroy，但这会导致不同的问题）。或者，用 Rust 的术语来说，我们会给他们一个 reference 而不是 owned value。这将有一个明显的缺点，即他们将无法更改它：在某些情况下，他们可能需要这样做，然后第二个选项可能更可取。
尝试在代码中对其进行建模会给我们带来一些错误：
T: Fn(K) -> V,
// Replace with
T: Fn(&K) -> V,
// And
fn value(&mut self, arg: K) -> &V {
if let Some(v) = self.values.get(&arg) {
v
} else {
let v = (self.calculation)(&arg);
self.values.insert(arg, v);
&v
}
}
error[E0502]: cannot borrow `self.values` as mutable because it is also borrowed as immutable
--> src/lib.rs:29:13
|
24 | fn value(&mut self, arg: K) -> &V {
| - let's call the lifetime of this reference `'1`
25 | if let Some(v) = self.values.get(&arg) {
| --------------------- immutable borrow occurs here
26 | v
| - returning this value requires that `self.values` is borrowed for `'1`
...
29 | self.values.insert(arg, v);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
error[E0515]: cannot return reference to local variable `v`
--> src/lib.rs:30:13
|
30 | &v
| ^^ returns a reference to data owned by the current function
error[E0382]: borrow of moved value: `v`
--> src/lib.rs:30:13
|
28 | let v = (self.calculation)(&arg);
| - move occurs because `v` has type `V`, which does not implement the `Copy` trait
29 | self.values.insert(arg, v);
| - value moved here
30 | &v
| ^^ value borrowed here after move
这有点过分了！
第一个错误实际上是 Rust 借用检查器的当前限制：代码没有编译器认为存在的问题，但编译器无法证明这一点。 Future projects are going to help the compiler figure it, but in the meantime, there is something we can do: Rust's hashmap has a construct designed exactly for this situation of insert-if-not-already-there: the entry API. Using it, our code looks like (playground):
fn value(&mut self, arg: K) -> &V {
// `&self.calculation` is really equal here to `|arg| (self.calculation)(arg)`, just shorter.
self.values.entry(arg).or_insert_with_key(&self.calculation)
}
神奇的是，我们还解决了另外两个问题！很好，但为了知识起见，我仍然会解释问题所在。
我们将v移动到hashmap中，然后使用它。这就是问题。再次考虑 v 具有类型 Vec<i32> 的情况。如果我们可以使用它，我们需要在之后销毁它 - 但它在地图内部，我们无法销毁它！出于这个原因，编译器拒绝了我们的代码并出现第三个错误。
至于第二个错误，我们return参考了v。但是 v 是一个局部变量，在函数结束时被销毁 - 所以我们会 return 引用无效数据！
修复它们 non-trivial（甚至不可能），所以我不想在这里解释它。
第二种解决方法是首先思考“为什么它适用于 i32、non-generic 版本？
答案很简单：之所以有效，是因为“摧毁”i32 不会造成任何伤害。更正式地说，i32 不持有某些资源，如 Vec 持有分配：它只是普通数据，复制它 - 只是按位，简单的复制 - 总是没问题的。或者，用 Rust 术语来说，i32 实现了 Copy.
这就提出了一个问题：我们可以在通用版本中表达这个规则吗？即说“我们只想允许复制始终有效的类型，即 实现 Copy？”事实证明，答案是，是的！我们只需要添加一个 where Type: Copy 绑定 (playground):
where
T: Fn(K) -> V,
K: Eq + Hash + Copy,
V: Copy,
有一种方法可以概括这一点：目前，这只允许 按位复制 - 也就是说，只允许可以自由复制完全相同位模式的类型。但是我们也可以允许 custom-copy 代码，并且允许像 Vec 这样的东西，在持有资源的同时，可以通过分配新内存和复制内容来复制。该特征称为 Clone，但它要求我们在复制值时更明确一点（注意每个 Copy 也是 Clone，因此它也适用于类型如 i32):
where
T: Fn(K) -> V,
K: Eq + Hash + Clone,
V: Clone,
fn value(&mut self, arg: K) -> V {
if let Some(v) = self.values.get(&arg) {
v.clone()
} else {
let v = (self.calculation)(arg.clone());
self.values.insert(arg, v.clone());
v
}
}
如果您对选择哪个选项有疑问，或者您不知道代码的客户需要什么，请选择第一个选项。它更通用，因为它允许任何类型（不仅仅是那些实现 Clone 的类型），如果他们需要它，他们总是可以 .clone() 值然后改变它，即使这有点不方便.