实现树型数据结构

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