我应该如何重构我的图形代码以避免“一次不能多次借用可变变量”错误？

Question

我有一个成功编译的简单图表：

use std::collections::HashMap;

type Key = usize;
type Weight = usize;

#[derive(Debug)]
pub struct Node<T> {
    key: Key,
    value: T,
}
impl<T> Node<T> {
    fn new(key: Key, value: T) -> Self {
        Node {
            key: key,
            value: value,
        }
    }
}

#[derive(Debug)]
pub struct Graph<T> {
    map: HashMap<Key, HashMap<Key, Weight>>,
    list: HashMap<Key, Node<T>>,
    next_key: Key,
}
impl<T> Graph<T> {
    pub fn new() -> Self {
        Graph {
            map: HashMap::new(),
            list: HashMap::new(),
            next_key: 0,
        }
    }
    pub fn add_node(&mut self, value: T) -> &Node<T> {
        let node = self.create_node(value);
        node
    }

    fn create_node(&mut self, value: T) -> &Node<T> {
        let key = self.get_next_key();
        let node = Node::new(key, value);
        self.list.insert(key, node);
        self.map.insert(key, HashMap::new());
        self.list.get(&key).unwrap()
    }

    fn get_next_key(&mut self) -> Key {
        let key = self.next_key;
        self.next_key += 1;
        key
    }
}

但是当我使用它时却无法编译：

fn main() {
    let mut graph = Graph::<i32>::new();
    let n1 = graph.add_node(111);
    let n2 = graph.add_node(222);
}

错误：

use std::collections::HashMap;

type Key = usize;
type Weight = usize;

#[derive(Debug)]
pub struct Node<T> {
    key: Key,
    value: T,
}
impl<T> Node<T> {
    fn new(key: Key, value: T) -> Self {
        Node {
            key: key,
            value: value,
        }
    }
}

#[derive(Debug)]
pub struct Graph<T> {
    map: HashMap<Key, HashMap<Key, Weight>>,
    list: HashMap<Key, Node<T>>,
    next_key: Key,
}
impl<T> Graph<T> {
    pub fn new() -> Self {
        Graph {
            map: HashMap::new(),
            list: HashMap::new(),
            next_key: 0,
        }
    }
    pub fn add_node(&mut self, value: T) -> &Node<T> {
        let node = self.create_node(value);
        node
    }

    fn create_node(&mut self, value: T) -> &Node<T> {
        let key = self.get_next_key();
        let node = Node::new(key, value);
        self.list.insert(key, node);
        self.map.insert(key, HashMap::new());
        self.list.get(&key).unwrap()
    }

    fn get_next_key(&mut self) -> Key {
        let key = self.next_key;
        self.next_key += 1;
        key
    }
}

我见过所有类似的问题。我知道这是失败的，因为方法Graph::add_node()使用了&mut self. 在所有类似的问题中，一般的答案是“重组你的代码”。我不明白我应该做什么？我应该如何重构这段代码？

Answer 1

通过返回&Node<T>from add_node，您实际上锁定了整个Graph<T>对象，因为您正在借用它。这是有充分理由的；尝试运行这个main：

fn main() {
    let mut graph = Graph::<i32>::new();
    let n1 = graph.add_node(111) as *const _;
    let mut inserts = 0;
    loop {
        inserts += 1;
        graph.add_node(222);
        let n1bis = graph.list.get(&0).unwrap() as *const _;
        if n1 != n1bis {
            println!("{:p} {:p} ({} inserts)", n1, n1bis, inserts);
            break;
        }
    }
}

以下是该程序可能的输出：

0x7f86c6c302e0 0x7f86c6c3a6e0 (29 inserts)

该程序添加第一个节点并将其地址存储为原始指针（原始指针没有生命周期参数，因此释放Graph了借用）。然后，它添加更多节点，一次一个，然后再次获取第一个节点的地址。如果第一个节点的地址发生更改，它将打印这两个地址以及插入到图中的其他节点的数量。

HashMap使用随机散列，因此每次执行时插入的数量都会有所不同。然而，它最终需要重新分配内存来存储更多条目，因此最终，映射中节点的地址会发生变化。如果您在发生这种情况后尝试取消引用旧指针（例如n1），那么您将访问已释放的内存，这可能会返回垃圾数据或导致错误（通常是分段错误）。

了解了这一切，应该清楚add_node不应返回&Node<T>. 以下是一些替代方案：

• 不返回任何内容add_node，或者返回Key，并提供一个单独的方法来获取给&Node<T>定的密钥。
• 将节点包裹在Rc<T>或中Arc<T>。也就是说，它不是list一个，而是一个。您可以使用或来复制指针并增加引用计数；将一份副本存储在 中，并从 中返回另一副本。 HashMap<Key, Node<T>>HashMap<Key, Rc<Node<T>>>clone()RcArcHashMapadd_node
  • 如果您还需要在保留改变图的能力的同时改变节点，则可能需要Rc与RefCell、 或Arcwith结合使用Mutex。