Как я должен реструктурировать свой код графа, чтобы избежать ошибки «Заменить заемную переменную как измененную более одного раза за раз»?

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

Ошибка:

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. Во всех подобных вопросах общий ответ - «перестроить свой код». Я не понимаю, что мне делать? Как мне переделать этот код?

Answer 1

По возвращении &Node<T> от 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 использует рандомизированный хеш, поэтому количество вставок будет меняться при каждом выполнении. Тем не менее, он будет в конечном итоге необходимо перераспределить память для хранения большего количества записей, поэтому, в конечном итоге, адрес узлов на карте изменится. Если вы попытались разыграть старый указатель (например,), после этого вы получите доступ к освобожденной памяти, которая может возвращать данные мусора или вызывать ошибку (обычно это ошибка сегментации).

Зная все это, должно быть ясно, что не должен возвращать &Node<T>. Вот несколько альтернатив:

• Сделайте add_node возвращение ничего, или вернуть Key и обеспечить отдельный метод получения &Node<T> дали ключ.
• Оберните свои узлы в Rc<T> или Arc<T>. То есть вместо list будет HashMap<Key, Node<T>>, это будет HashMap<Key, Rc<Node<T>>>. Вы можете clone() a Rc или Arc скопировать указатель и увеличить счетчик ссылок; сохраните одну копию в HashMap и верните другую копию с add_node.
  • Если вы также должны мутировать узлы, сохраняя при этом способность мутировать график, возможно, потребуется объединить Rc с RefCell или Arc с Mutex.

Answer 2

Я решил проблему с помощью std::rc::Rc:

use std::collections::HashMap; 
use std::rc::Rc; 

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, Rc<Node<T>>>, // <-- Changed 
    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) -> Rc<Node<T>> { 
     // <-- Changed 
     let key = self.get_next_key(); 
     let node = Rc::new(Node::new(key, value)); // <-- Changed 
     self.list.insert(key, node.clone()); // <-- Changed 
     self.map.insert(key, HashMap::new()); 
     node 
    } 

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