實現樹型數據結構

Question

我想實現一個樹型數據結構。我有一個Node結構，並希望它保存對子代Node的引用。我想：

use std::collections::*; 

#[derive(Debug)] 
struct Node { 
    value: String, 
    children: HashMap<String, Node>, 
} 


impl Node { 
    fn new(value: String) -> Self { 
     Node { 
      value: value, 
      children: HashMap::new(), 
     } 
    } 

    fn add_child(&mut self, key: String, value: String) -> &mut Node { 
     let mut node = Node::new(value); 
     self.children.insert(key, node); 
     &mut node 
    } 
} 


fn main() { 
    let mut root_node = Node::new("root".to_string()); 
    root_node.add_child("child_1_1".to_string(), "child_1_1_value".to_string()); 
} 

此代碼不能編譯：

error: `node` does not live long enough 
    --> src/main.rs:22:10 
    | 
22 |  &mut node 
    |   ^^^^ does not live long enough 
23 | } 
    | - borrowed value only lives until here 
    | 
note: borrowed value must be valid for the anonymous lifetime #1 defined on the body at 19:67... 
    --> src/main.rs:19:68 
    | 
19 |  fn add_child(&mut self, key: String, value: String) -> &mut Node { 
    | ____________________________________________________________________^ starting here... 
20 | |  let mut node = Node::new(value); 
21 | |  self.children.insert(key, node); 
22 | |  &mut node 
23 | | } 
    | |___^ ...ending here 

error[E0382]: use of moved value: `node` 
    --> src/main.rs:22:10 
    | 
21 |  self.children.insert(key, node); 
    |        ---- value moved here 
22 |  &mut node 
    |   ^^^^ value used here after move 
    | 
    = note: move occurs because `node` has type `Node`, which does not implement the `Copy` trait 

我如何能實現呢？

Answer 1

在這種情況下，它實際上就要看在編譯器輸出的秒錯誤消息：

error[E0382]: use of moved value: `node` 
    --> src/main.rs:22:10 
    | 
21 |  self.children.insert(key, node); 
    |        ---- value moved here 
22 |  &mut node 
    |   ^^^^ value used here after move 
    | 
    = note: move occurs because `node` has type `Node`, which does not implement the `Copy` trait 

變量node移動爲在行21 HashMap中你不能之後使用它！在Rust中，我們有移動語義，這意味着默認情況下所有內容都被移動，而不是默認（C++）克隆或默認引用（Java）。你想要返回一個對象的引用裏面的這個hashmap！

一個簡單的方法是將插入node因爲你已經這樣做，之後從HashMap中提取值：

let mut node = Node::new(value); 
self.children.insert(key.clone(), node); 
self.children.get_mut(key).unwrap() 

這應該明確哪些功能實際上不會。但是，這段代碼有一些缺點：首先，我們必須克隆key（我們需要它來插入和查詢），其次，哈希映射需要計算兩次密鑰的哈希，這不是非常有效。

幸運的是，Rust的HashMap有一個不錯的entry()-API。我們可以改變功能類似：

self.children.entry(key).or_insert_with(|| Node::new(value)) 

這是add_child()整個身體！但是，現在我們注意到......如果散列圖已經包含一個與給定鍵相關聯的值，那麼我們並沒有真正考慮應該發生什麼！在上面的代碼中，舊值保留並返回。如果你想做些別的事情（如更換值），你可以只在Entry對象使用match：

let node = Node::new(value); 
match self.children.entry(key) { 
    Entry::Occupied(e) => { 
     // Maybe you want to panic!() here... but we will just 
     // replace the value: 
     e.insert(node); // discarding old value... 
     e.get_mut() 
    } 
    Entry::Vacant(e) => insert(node), 
}