HashMap在尝试实现查找或插入时的借用问题

Question

HashMap在尝试实现查找或插入时的借用问题

4

我尝试实现自己的find_or_insert方法，它看起来像这样：

use std::collections::HashMap;

pub struct SomeManager {
    next: i32,
    types: HashMap<i32, i32>,
}

impl SomeManager {
    pub fn get_type<'a>(&'a mut self, k: i32) -> &'a i32 {
        match self.types.get(&k) {
            Some(ref x) => return *x,
            None => {
                self.types.insert(k, self.next);
                self.next += 1;
                return self.types.get(&k).unwrap();
            }
        }
    }
}

fn main() {}

错误：

error[E0502]: cannot borrow `self.types` as mutable because it is also borrowed as immutable
  --> src/main.rs:13:17
   |
10 |         match self.types.get(&k) {
   |               ---------- immutable borrow occurs here
...
13 |                 self.types.insert(k, self.next);
   |                 ^^^^^^^^^^ mutable borrow occurs here
...
18 |     }
   |     - immutable borrow ends here

我知道有一些标准方法可以实现这个功能，但我希望这个方法尽可能轻量级 - 它将被频繁调用，而且几乎所有的值都已经存在。

据我所知，当我们调用self.types.get时，我们将其借用到match语句的范围内，因此我们无法在此处调用self.types.insert。我试图将方法从None分支移到match语句之外，但也失败了。

我找到的唯一有效的解决方案需要两次调用get：

pub fn get_type<'a>(&'a mut self, k: i32) -> &'a i32 {
    let is_none = match self.types.get(&k) {
        Some(ref x) => false,
        None => true,
    };
    if is_none {
        self.types.insert(k, self.next);
        self.next += 1;
    }
    self.types.get(&k).unwrap()
}

如何绕过这种情况？

- Mikhail

2个回答

1

请注意，在第一种情况下，当键存在于映射中时，您进行了一次查找，而在不存在时则进行了三次查找。您的最后一次尝试在任何情况下都会进行两次查找。这是后者的某种美化版本：

pub fn get_type<'a>(&'a mut self, k: i32) -> &'a i32 {
    let contains = self.types.contains_key(&k);
    if !contains {
        self.types.insert(k, self.next);
        self.next += 1;
    }
    self.types.get(&k).unwrap()
}

我认为在没有地图实现的支持下，由于借用限制，不可能避免第二次查找。

无论如何，使用 Chris Morgan的解决方案比上面的方法更优（例如，它可能更有效率，实际上需要更少的查找），所以建议坚持使用它。

- Vladimir Matveev

第二个解决方案对我来说是理想的，但它也无法编译 - 出于某种原因，它说匹配中的先前借用（borrow）在函数末尾结束。 - Mikhail

@Mikhail，看看这个。 - Vladimir Matveev

返回一个引用意味着 v 的生命周期是 'a，因此 self.types 借用的生命周期也是 'a ——你放在它周围的花括号完全没有帮助。 - Chris Morgan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Morgan · Accepted Answer

在HashMap上有几种方法可以实现这些复杂情况。特别是对于您的情况，最值得注意的是 HashMap::entry 和 Entry::or_insert_with 方法：

pub fn get_type<'a>(&'a mut self, k: i32) -> &'a i32 {
    self.types.entry(k).or_insert_with(|| {
        let value = self.next;
        self.next += 1;
        value
    })
}

然而在您的情况下，内部存在self的借用，这样做不行。

因此，我们将self.next的借用移至闭包之外，以便编译器可以将其视为与self.types不相交。问题得到解决，只需要进行一次查找，就像应该做的那样。

pub fn get_type<'a>(&'a mut self, k: i32) -> &'a i32 {
    let next = &mut self.next;

    self.types.entry(k).or_insert_with(|| {
        let value = *next;
        *next += 1;
        value
    })
}