从同一个HashMap中借用两个可变值

Question

我有以下代码:

use std::collections::{HashMap, HashSet};

fn populate_connections(
    start: i32,
    num: i32,
    conns: &mut HashMap<i32, HashSet<i32>>,
    ancs: &mut HashSet<i32>,
) {
    let mut orig_conns = conns.get_mut(&start).unwrap();
    let pipes = conns.get(&num).unwrap();

    for pipe in pipes.iter() {
        if !ancs.contains(pipe) && !orig_conns.contains(pipe) {
            ancs.insert(*pipe);
            orig_conns.insert(*pipe);
            populate_connections(start, num, conns, ancs);
        }
    }
}

fn main() {}

逻辑不是很重要,我正在尝试创建一个本身并遍历管道的函数.

我的问题是这不编译:

error[E0502]: cannot borrow `*conns` as immutable because it is also borrowed as mutable
  --> src/main.rs:10:17
   |
9  |     let mut orig_conns = conns.get_mut(&start).unwrap();
   |                          ----- mutable borrow occurs here
10 |     let pipes = conns.get(&num).unwrap();
   |                 ^^^^^ immutable borrow occurs here
...
19 | }
   | - mutable borrow ends here

error[E0499]: cannot borrow `*conns` as mutable more than once at a time
  --> src/main.rs:16:46
   |
9  |     let mut orig_conns = conns.get_mut(&start).unwrap();
   |                          ----- first mutable borrow occurs here
...
16 |             populate_connections(start, num, conns, ancs);
   |                                              ^^^^^ second mutable borrow occurs here
...
19 | }
   | - first borrow ends here

我不知道如何让它发挥作用.一开始,我试图将两个HashSet存储在HashMap(orig_conns和pipes)中.

Rust不会让我同时拥有可变和不可变的变量.我有点困惑,因为这将是完全不同的对象,但我想如果&start== &num,那么我会对同一个对象有两个不同的引用(一个是可变的,一个是不可变的).

多数民众赞成,但那我怎么能做到这一点？我想迭代一个HashSet并阅读和修改其他一个.我们假设他们不会是一样的HashSet.

Answer 1

如果您可以更改数据类型和函数签名,则可以使用a RefCell来创建内部可变性:

use std::cell::RefCell;
use std::collections::{HashMap, HashSet};

fn populate_connections(
    start: i32,
    num: i32,
    conns: &HashMap<i32, RefCell<HashSet<i32>>>,
    ancs: &mut HashSet<i32>,
) {
    let mut orig_conns = conns.get(&start).unwrap().borrow_mut();
    let pipes = conns.get(&num).unwrap().borrow();

    for pipe in pipes.iter() {
        if !ancs.contains(pipe) && !orig_conns.contains(pipe) {
            ancs.insert(*pipe);
            orig_conns.insert(*pipe);
            populate_connections(start, num, conns, ancs);
        }
    }
}

fn main() {}

请注意,如果start == num该线程将发生混乱,因为这是尝试同时具有可变和不可变的访问权限HashSet.

安全的替代品 RefCell

根据您的确切数据和代码需求,您还可以使用类型Cell或其中一个原子.它们的内存开销低于a RefCell,而且对codegen的影响很小.

在多线程情况下,您可能希望使用Mutex或RwLock.

Answer 2

用 hashbrown::HashMap

如果您可以切换到使用 hashbrown，则可以使用如下方法get_each_mut：

use hashbrown::HashMap; // 0.11.2 features=["nightly"]

fn main() {
    let mut map = HashMap::new();
    map.insert(1, true);
    map.insert(2, false);

    dbg!(&map);

    if let [Ok(a), Ok(b)] = map.get_each_mut([&1, &2]) {
        std::mem::swap(a, b);
    }

    dbg!(&map);
}

不安全代码

如果你能保证你的两个索引是不同的，你可以使用不安全的代码并避免内部可变性：

use std::collections::HashMap;

fn get_mut_pair<'a, K, V>(conns: &'a mut HashMap<K, V>, a: &K, b: &K) -> (&'a mut V, &'a mut V)
where
    K: Eq + std::hash::Hash,
{
    unsafe {
        let a = conns.get_mut(a).unwrap() as *mut _;
        let b = conns.get_mut(b).unwrap() as *mut _;
        assert_ne!(a, b, "The two keys must not resolve to the same value");
        (&mut *a, &mut *b)
    }
}

fn main() {
    let mut map = HashMap::new();
    map.insert(1, true);
    map.insert(2, false);

    dbg!(&map);

    let (a, b) = get_mut_pair(&mut map, &1, &2);
    std::mem::swap(a, b);

    dbg!(&map);
}

类似的代码可以在multi_mut 等库中找到。

这段代码试图非常谨慎。断言强制要求两个值在将它们转换回可变引用之前是不同的指针，并且我们显式地为返回的变量添加生命周期。

在盲目使用此解决方案之前，您应该了解不安全代码的细微差别。值得注意的是，此答案的先前版本是不正确的。感谢@oberien 发现了这个最初实现中的不健全之处并提出了修复方案。这个游乐场展示了纯粹安全的 Rust 代码如何导致旧代码导致内存不安全。

此解决方案的增强版本可以接受一组键并返回一组值：

fn get_mut_pair<'a, K, V, const N: usize>(conns: &'a mut HashMap<K, V>, mut ks: [&K; N]) -> [&'a mut V; N]

然而，确保所有传入的密钥都是唯一的变得更加困难。

请注意，此函数不会尝试解决原始问题，这比验证两个索引是否不相交要复杂得多。原题要求：

• 跟踪三个不相交的借用，其中两个是可变的，一个是不可变的。
• 跟踪递归调用
  • 不得修改 HashMap以任何会导致调整大小的方式，这将使上一级别的任何现有引用无效。
  • 不得为前一级别的任何引用设置别名。

使用类似的方法RefCell是一种更简单的方法，可确保您不会触发内存不安全。