Strukturdatenstruktur implementieren

Question

Ich möchte eine Baumdatenstruktur implementieren. Ich habe eine Node Struktur und möchte, dass es Referenzen auf Kind Node s hält. Ich habe versucht:

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

Dieser Code nicht kompiliert:

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 

Wie kann ich das umsetzen?

Answer 1

In diesem Fall ist es tatsächlich notwendig, an der Sekunden Fehlermeldung im Compiler Ausgabe aussehen:

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 

Die Variable node bewegt wird in die hashmap in Zeile 21. Sie können nicht benutze es danach! In Rust haben wir move semantics, was bedeutet, dass alles standardmäßig verschoben statt standardmäßig geklont (C++) oder standardmäßig (Java) referenziert wird. Sie möchten eine Referenz auf das Node Objekt innerhalb der hashmap zurückgeben!

Eine einfache Möglichkeit wäre node einfügen, wie Sie bereits tun, und danach den Wert aus dem hashmap holen:

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

Diese deutlich machen sollte, was die Funktion tut eigentlich. Allerdings hat dieser Code einige Nachteile: Zuerst müssen wir key klonen (wir brauchen es für die Einfügung und die Abfrage) und zweitens muss die Hashmap den Hash des Schlüssels zweimal berechnen, was nicht sehr effizient ist.

Glücklicherweise hat Rust HashMap eine nette entry()-API. Wir könnten die Funktion wie das ändern:

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

Dies ist der ganze Körper von add_child()! Jetzt bemerken wir jedoch, dass ... wir nicht wirklich darüber nachgedacht haben, was passieren soll, wenn die Hashmap bereits einen Wert enthält, der dem gegebenen Schlüssel zugeordnet ist! Im obigen Code wird der alte Wert beibehalten und zurückgegeben. Wenn Sie etwas anderes (zB ersetzen Sie den Wert) tun möchten, können Sie einfach match auf dem Entry Objekt verwenden:

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