How to avoid temporary allocations when using a complex key for a HashMap?

Question

I'm using a complex key for HashMap such that the key comprises two parts and one part is a String, and I can't figure out how to do lookups via the HashMap::get method without allocating a new String for each lookup.

Here's some code:

#[derive(Debug, Eq, Hash, PartialEq)]
struct Complex {
    n: i32,
    s: String,
}

impl Complex {
    fn new<S: Into<String>>(n: i32, s: S) -> Self {
        Complex { n: n, s: s.into() }
    }
}

fn main() {
    let mut m = std::collections::HashMap::<Complex, i32>::new();
    m.insert(Complex::new(42, "foo"), 123);

    // OK, but allocates temporary String
    assert_eq!(123, *m.get(&Complex::new(42, "foo")).unwrap());
}

The problem is with the final assertion. It passes, but it requires a temporary heap allocation because I cannot construct a Complex without constructing a String.

To eliminate temporary allocations like this, Rust provides the Borrow trait, which the HashMap::get method makes use of. I understand how to make Borrow work for simple keys. For example, the Rust Standard Library's PathBuf implements Borrow<Path> by making use of std::mem::transmute under the hood, but I can't figure out how to make it work for my Complex type:

#[derive(Debug)]
struct Borrowable {
    // ??? -- What goes here? Perhaps something like:
    n: i32,
    s1: &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: &str) -> &Self {
         // ??? -- What goes here? It must not allocate.
        unimplemented!();
    }
}

impl std::borrow::Borrow<Borrowable> for Complex {
    fn borrow(&self) -> &Borrowable {
        // ??? -- What goes here? How can I transmute a Complex into a
        //        &Borrowable?
        unimplemented!();
    }
}

This seems like a common use case, and I suspect I'm missing something important about Borrow, but I'm at a total loss.

Answer 1

It sounds like you want this.

Cow will accept a &str or String.

use std::borrow::Cow;

#[derive(Debug, Eq, Hash, PartialEq)]
struct Complex<'a> {
    n: i32,
    s: Cow<'a, str>,
}

impl<'a> Complex<'a> {
    fn new<S: Into<Cow<'a, str>>>(n: i32, s: S) -> Self {
        Complex { n: n, s: s.into() }
    }
}

fn main() {
    let mut m = std::collections::HashMap::<Complex<'_>, i32>::new();
    m.insert(Complex::new(42, "foo"), 123);

    assert_eq!(123, *m.get(&Complex::new(42, "foo")).unwrap());
}

A comment about lifetime parameters:

If you don't like the lifetime parameter and you only need to work with &'static str or String then you can use Cow<'static, str> and remove the other lifetime parameters from the impl block and struct definition.