title: "borrowed value does not live long enough" error in trie insertion
body: <p>I have a simple trie implementation where an <code>Edge</code> contains a character and a reference to another <code>Node</code>:</p>
  
  <pre><code>struct Edge&lt;'a&gt; {
      ch: char,
      to: &amp;'a Node&lt;'a&gt;,
  }
  </code></pre>
  
  <p>A <code>Node</code> contains a vector of edges:</p>
  
  <pre><code>pub struct Node&lt;'a&gt; {
      edges: Vec&lt;Edge&lt;'a&gt;&gt;,
  }
  </code></pre>
  
  <p>I'm trying to implement the method to insert/get a character into a node. I think the return value should be a reference to a <code>Node</code>: if the character is already in one of the edges, then we directly return the existing <code>Node</code>; if not, we return the newly created <code>Node</code>. This is where I get into trouble:</p>
  
  <pre><code>impl&lt;'a&gt; Node&lt;'a&gt; {
      fn get_or_create(&amp;mut self, ch: char) -&gt; &amp;Node&lt;'a&gt; {
          match self.edges.binary_search_by(|e| e.ch.cmp(&amp;ch)) {
              Ok(idx) =&gt; {
                  return &amp;self.edges.get(idx).unwrap().to;
              }
              Err(idx) =&gt; {
                  let to = &amp;Node { edges: Vec::new() };
                  let e = Edge { ch: ch, to: to };
                  self.edges.insert(idx, e);
                  return to;
              }
          }
      }
  }
  </code></pre>
  
  <p>The <code>to</code> is said to not live long enough.</p>
  
  <p>I'm quite sure what I wrote is far from idiomatic Rust. Initially when I included the reference to <code>Node</code> in <code>Edge</code>, I didn't add the lifetime parameter, and was prompted to do so, then I had to add it everywhere. However it looks quite weird. I wonder what would be the correct way to do it?</p>
  
  <p>Maybe what I should really have used is some other wrapper type abstraction in <code>Edge</code> to refer to heap-allocated <code>Node</code>, e.g. <code>Box</code>? I shall read the section on this topic in <em>The Rust Programming Language</em> carefully.</p>