How to get value from a map using tuple of str references for a custom struct

Assume I have the below code

struct MapKey {
    v1: String,
    v2: String,
}

impl PartialEq<(&str, &str)> for MapKey {
    fn eq(&self, other: &(&str, &str)) -> bool { 
        &self.v1 == other.0 && &self.v2 == other.1
    }
}

let my_map = HashMap<MapKey, String>::new();

How to get value from a map using string references for v1 and v2 like below

v1 = "someV1"
v2 = "someV2"

my_map.get((v1, v2)) // This the part I am struggling to implement

The reason for above is beacuse I would like to abvoid creating owned instances of v1 and v2 for fetching the value from my_map.

Thanks for the help in advance

Let's take a look at the documentation for HashMap::get():

pub fn get<Q>(&self, k: &Q) -> Option<&V>
where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Returns a reference to the value corresponding to the key.

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

In your case, K (the type of the keys stored in the HashMap) is MapKey, and Q (the type you want to pass to get()) is (&str, &str). So all you need to do is implement Borrow<(&str, &str)> for MapKey, and then you can do my_map.get(&(v1, v2)) (Note the addition of the & on the tuple).

Caveat: I'm not entirely sure how to interpret the requirement that "Hash ... on the borrowed form must match ... the key type". Does it mean that, for all key values key1 and key2, if (and only if?) hash(key1) == hash(key2), then hash(borrow(key1)) == hash(borrow(key2))? If so, you should be good as long as you don't add any fields to MapKey and stick with the derived Hash impl. Or does it mean that, for all key values key, hash(key) must equal hash(borrow(key))? I'm not sure if that can be guaranteed; as far as I know, derived Hash impls on structs are not required to work the same way as the Hash impl on a tuple of the struct's field.

Hello,

I have edited the code in the question to reflect the PartialEq I am implementing for it and I am using the default derived hash implementation.

I also went through the doc and tried to implement the borrow trait but I start getting these lifetime errors.

   Compiling playground v0.0.1 (/playground)
error: `impl` item signature doesn't match `trait` item signature
   --> src/main.rs:17:5
    |
17  |     fn borrow(&self) -> &(&str, &str) { todo!() }
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ found `fn(&'1 MapKey) -> &'1 (&'1 str, &'1 str)`
    |
   ::: /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/borrow.rs:178:5
    |
178 |     fn borrow(&self) -> &Borrowed;
    |     ------------------------------ expected `fn(&'1 MapKey) -> &'1 (&'3 str, &str)`
    |
    = note: expected signature `fn(&'1 MapKey) -> &'1 (&'3 str, &str)`
               found signature `fn(&'1 MapKey) -> &'1 (&'1 str, &'1 str)`
    = help: the lifetime requirements from the `impl` do not correspond to the requirements in the `trait`
    = help: verify the lifetime relationships in the `trait` and `impl` between the `self` argument, the other inputs and its output

error: could not compile `playground` (bin "playground") due to previous error

playground link -> Rust Playground

If I sepcify a lifetime for it I get

Standard Error

   Compiling playground v0.0.1 (/playground)
error[E0308]: method not compatible with trait
  --> src/main.rs:17:5
   |
17 |     fn borrow(&'a self) -> &(&'a str, &'a str) { todo!() }
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
   |
   = note: expected signature `fn(&MapKey) -> &(&'a str, &'a str)`
              found signature `fn(&'a MapKey) -> &'a (&'a str, &'a str)`
note: the anonymous lifetime as defined here...
  --> src/main.rs:17:5
   |
17 |     fn borrow(&'a self) -> &(&'a str, &'a str) { todo!() }
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...does not necessarily outlive the lifetime `'a` as defined here
  --> src/main.rs:16:6
   |
16 | impl<'a> Borrow<(&'a str, &'a str)> for MapKey {
   |      ^^

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` (bin "playground") due to previous error

playground link -> Rust Playground

Thats where I am stuck at

Use a more-flexible HashMap:

use hashbrown::{Equivalent, HashMap};

#[derive(Hash, Eq, PartialEq)]
struct MapKey {
    v1: String,
    v2: String,
}

impl Equivalent<MapKey> for (&str, &str) {
    fn equivalent(&self, key: &MapKey) -> bool {
        self.0 == key.v1 && self.1 == key.v2
    }
}

fn main() {
    let mut my_map = HashMap::<MapKey, String>::new();
    my_map.insert(
        MapKey {
            v1: "foo".into(),
            v2: "bar".into(),
        },
        "baz".into(),
    );
    let v = my_map.get(&("foo", "bar"));
    dbg!(v);
}
3 Likes

Thank you, works like a charm

There’s also a more tedious and less efficient workaround for std’s HashMap API involving trait objects. It does avoid allocations, but also avoids some dynamic function calls which probably won’t optimize away fully.

The usage of hashbrown and its more general API for this is very much the preferred approach. Still, for educational purposes, I think it’s interesting to take a look at what the workaround would take:

The trick here is that we need to implement Borrow so that we can create a fn(&MapKey) -> &Something conversion to some type Something, but we’ll also need to be able to create a &Something reference from our (&str, &str). The strict requirements of fn(&MapKey) -> &Something force us that we cannot somehow incorporate more than a single reference into the return type; yet (&str, &str) can never be made to match a &MapKey reference type, unless we can make different types the same somehow, which is is what trait objects allow.

By implementing MapKeyTrait for MapKey, we can turn &MapKey into &dyn MapKeyTrait trivially in the Borrow implementation; if we also implement it for (&str, &str), we can create a &dyn MapKeyTrait for it, without allocations, too. Finally, implementing both (PartialEq + ) Eq and Hash for dyn MapKeyTrait itself completes the workaround – for this, the trait gets methods to get a &str view of each of the two fields, and for simplicity we can do this using a single method and re-using Eq and Hash implementations of (&str, &str) itself.

use std::collections::HashMap;

#[derive(Hash, Eq, PartialEq)]
struct MapKey {
    v1: String,
    v2: String,
}

trait MapKeyTrait {
    fn as_strs(&self) -> (&str, &str);
}
impl MapKeyTrait for MapKey {
    fn as_strs(&self) -> (&str, &str) {
        (&self.v1, &self.v2)
    }
}
impl<'a> std::borrow::Borrow<dyn MapKeyTrait + 'a> for MapKey {
    fn borrow(&self) -> &(dyn MapKeyTrait + 'a) {
        self
    }
}

impl MapKeyTrait for (&str, &str) {
    fn as_strs(&self) -> (&str, &str) {
        *self
    }
}

impl std::hash::Hash for dyn MapKeyTrait + '_ {
    fn hash<H>(&self, state: &mut H) where H: std::hash::Hasher {
        self.as_strs().hash(state)
    }
}
impl std::cmp::PartialEq for dyn MapKeyTrait + '_ {
    fn eq(&self, other: &dyn MapKeyTrait) -> bool {
        self.as_strs() == other.as_strs()
    }
}
impl std::cmp::Eq for dyn MapKeyTrait + '_ {}

fn main() {
    let mut my_map = HashMap::<MapKey, String>::new();
    my_map.insert(
        MapKey {
            v1: "foo".into(),
            v2: "bar".into(),
        },
        "baz".into(),
    );
    let v = my_map.get(&("foo", "bar") as &dyn MapKeyTrait);
    dbg!(v);
}
2 Likes

Here's another walkthrough on the trait object approach.

3 Likes

Thanks you for the explanation

Thank you for the explanation

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.