HashMap with tuple keys

[jamii]

How do I fill in this function without cloning a and b?

fn get(hashmap: HashMap<(String, String), i64>, a: &String, b: &String) -> Option<i64> {
  // ?
}

There doesn’t seem to be an impl Borrow<(&X, &Y)> for (X,Y) and I can’t implement it myself.

I’ve tried using a new struct struct TwoStrings{a: String, b: String} instead of a tuple, but I can’t seem get the lifetimes right for 'impl Borrow<(&String, &String)> for TwoStrings` either.

[dtolnay]

Here is one possible implementation. [playground]

use std::collections::HashMap;
use std::mem::ManuallyDrop;
use std::ptr;

fn get(map: HashMap<(String, String), i64>, a: &String, b: &String) -> Option<i64> {
    unsafe {
        // The 24-byte string headers of `a` and `b` may not be adjacent in
        // memory. Copy them (just the headers) so that they are adjacent. This
        // makes a `(String, String)` backed by the same data as `a` and `b`.
        let k = (ptr::read(a), ptr::read(b));

        // Make sure not to drop the strings, even if `get` panics. The caller
        // or whoever owns `a` and `b` will drop them.
        let k = ManuallyDrop::new(k);

        // Deref `k` to get `&(String, String)` and perform lookup.
        let v = map.get(&k);

        // Turn `Option<&i64>` into `Option<i64>`.
        v.cloned()
    }
}

fn main() {
    let mut map = HashMap::new();
    map.insert(("a".to_owned(), "b".to_owned()), 2);
    map.insert(("c".to_owned(), "d".to_owned()), 3);

    let a = "a".to_owned();
    let b = "b".to_owned();
    println!("{:?}", get(map, &a, &b));
}

[kamalmarhubi]

There was a post on the internals forum about extending how maps use Borrow for exactly this use case: https://internals.rust-lang.org/t/an-extension-of-hashmaps-use-of-borrow/4384

[kennytm]

There is a safe solution, at the cost of using a trait object (virtual dispatch), and you need to use a custom type like TwoStrings as the key instead of tuple, and lots of explanation.

[krdln]

Your solution (and stabilization of ManuallyDrop) has inspired me to create a little crate

krdln/fakestring

Here’s how the get function would look like with it:

    // Create a tuple with the same layout as the hashmap key
    let key = (FakeString::from(a), FakeString::from(b));

    // Convert from `&(FakeString, FakeString)` to `&(String, String)`
    map.get(key.unfake()).cloned()

I’d be happy if somebody could look at the implementation, especially wrt. safety.

Also, do you think it’s worth putting on crates.io?

[jamii]

The stackoverflow post also suggests using Cow<str>, which seems like the most pragmatic solution in the short-term.

[burns47]

I’ve tried using a new struct struct TwoStrings{a: String, b: String} instead of a tuple, but I can’t seem get the lifetimes right for 'impl Borrow<(&String, &String)> for TwoStrings` either.

I really recommend that you use this approach - you were on the right track. If you’ve got this struct, what’s the need to pass a tuple of two references?

See this:

use std::collections::HashMap;

#[derive(Eq, PartialEq, Hash, Clone)]
struct TwoStrings{
    a: String,
    b: String
}

pub fn main() {
    let mut map : HashMap<TwoStrings, i32> = HashMap::new();
    
    let key_one = TwoStrings{ a: "a".to_owned(), b: "b".to_owned() };
    let key_two = TwoStrings{ a: "c".to_owned(), b: "d".to_owned() };
    
    map.insert(key_one.clone(), 2i32);
    map.insert(key_two.clone(), 2i32);
    
    let entry = map.get(&key_one); //retrieve from the hashmap
}

[krdln]

If you’ve got this struct, what’s the need to pass a tuple of two references?

Indeed, if you have the struct there’s no need to split it into references. But OP is having problem when they don’t have the actual struct to use as a key, but only two separate references (a: &String, b: &String)

[burns47]

I see the problem now…writing an implementation of Borrow for TwoStrings that returns (&String, &String) appears to be impossible because Borrow requires us to return a reference - e.g. maybe &(&String, &String) - but in order to return a reference we have to have that tuple in the first place

This problem wouldn’t exist if Borrow let you return things that were conceptually borrows but weren’t actually borrows…

fn borrow(&self) -> T;

but I’m sure that introduces other problems! (I’ve included what that might look like here)

Sorry for sidetracking!

[vitalyd]

This looks like an impl<'a> Into<(&'a String, &'a String)> for &'a (String, String)?