title: How to avoid temporary allocations when using a complex key for a HashMap?
body: <p>I'm using a complex key for <code>HashMap</code> such that the key comprises two parts and one part is a <code>String</code>, and I can't figure out how to do lookups via the <code>HashMap::get</code> method without allocating a new <code>String</code> for each lookup.</p>
  
  <p>Here's some code:</p>
  
  <pre><code>#[derive(Debug, Eq, Hash, PartialEq)]
  struct Complex {
      n: i32,
      s: String,
  }
  
  impl Complex {
      fn new&lt;S: Into&lt;String&gt;&gt;(n: i32, s: S) -&gt; Self {
          Complex { n: n, s: s.into() }
      }
  }
  
  fn main() {
      let mut m = std::collections::HashMap::&lt;Complex, i32&gt;::new();
      m.insert(Complex::new(42, "foo"), 123);
  
      // OK, but allocates temporary String
      assert_eq!(123, *m.get(&amp;Complex::new(42, "foo")).unwrap());
  }
  </code></pre>
  
  <p>The problem is with the final assertion. It passes, but it requires a temporary heap allocation because I cannot construct a <code>Complex</code> without constructing a <code>String</code>.</p>
  
  <p>To eliminate temporary allocations like this, Rust provides the <a href="https://doc.rust-lang.org/std/borrow/trait.Borrow.html" rel="nofollow noreferrer"><code>Borrow</code></a> trait, which the <code>HashMap::get</code> method makes use of. I understand how to make <code>Borrow</code> work for simple keys. For example, the Rust Standard Library's <code>PathBuf</code> implements <code>Borrow&lt;Path&gt;</code> by making use of <code>std::mem::transmute</code> under the hood, but I can't figure out how to make it work for my <code>Complex</code> type:</p>
  
  <pre><code>#[derive(Debug)]
  struct Borrowable {
      // ??? -- What goes here? Perhaps something like:
      n: i32,
      s1: &amp;str, // ??? -- But what would the lifetime be? Or maybe:
      s2: str,  // ??? -- But how would I extend this to a complex type
                //        containing two or more strings?
  }
  
  impl Borrowable {
      fn new(n: i32, s: &amp;str) -&gt; &amp;Self {
           // ??? -- What goes here? It must not allocate.
          unimplemented!();
      }
  }
  
  impl std::borrow::Borrow&lt;Borrowable&gt; for Complex {
      fn borrow(&amp;self) -&gt; &amp;Borrowable {
          // ??? -- What goes here? How can I transmute a Complex into a
          //        &amp;Borrowable?
          unimplemented!();
      }
  }
  </code></pre>
  
  <p>This seems like a common use case, and I suspect I'm missing something important about <code>Borrow</code>, but I'm at a total loss.</p>