2

正常にコンパイルされる単純なグラフがあります。

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);
}

エラー：

error[E0499]: cannot borrow `graph` as mutable more than once at a time
  --> src/main.rs:57:14
   |
56 |     let n1 = graph.add_node(111);
   |              ----- first mutable borrow occurs here
57 |     let n2 = graph.add_node(222);
   |              ^^^^^ second mutable borrow occurs here
58 | }
   | - first borrow ends here

同様の質問をすべて見ました。Graph::add_node()メソッドが を使用しているため、それが失敗していることはわかっています&mut self。同様のすべての質問で、一般的な答えは「コードを再構築する」です。理解できません どうすればいいですか？このコードを再構築するにはどうすればよいですか?

4

2 に答える 2

4

&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は解放されます)。次に、一度に 1 つずつノードを追加し、最初のノードのアドレスを再度フェッチします。最初のノードのアドレスが変更された場合、両方のアドレスと、グラフに挿入された追加ノードの数が出力されます。

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()してポインターをコピーし、参照カウントをインクリメントできます。1 つのコピーを に保管し、もう 1 つのコピーをから返却します。 RcArcHashMapadd_node
    • グラフを変更する機能を保持しながらノードも変更する必要がある場合は、 、または と組み合わせる必要がある場合RcがRefCellありArcますMutex。
于 2016-04-13T02:46:52.483 に答える