Go from &Q to &K where K: Borrow<Q>

help
#1

I am trying to write a generic code over a collections::hash_map::HashMap.
While trying to follow the API of get which is:

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

my own get has the same signature. How do I reuse this k of type &Q when accessing the internal HashMap? For example, insert expect a real K, but all I have at hand is &Q.

pub fn insert(&mut self, k: K, v: V) -> Option<V>
#2

You can't, in general, go backwards like this. You'll need to find some other way to convert &Q -> K, maybe by defining your own traits, or something else. What's your signature for insert, maybe I can help find a solution?

#3

my code is a generic implementation of a struct wrapping a HashMap. I am trying to implement a cache, and so the cache should mutate the underlying map. Generally, it should not have an insert API.
Maybe I should change my get API trait bounds?

#4

One possibility is to restrict yourself to Q: ToOwned<Owned = K>.

Edit/Note: I’m semi-regularly disappointed by the fact that HashMap still doesn’t come with any API using ToOwned types itself. It could optimize them so that the “cloning” only happens when an insertion is actually needed. (An optimization that would be even more important/relevant when you’re working with the .entry() API.)

2 Likes
#5

So you have something like the following?

struct Cache<K, V> {
    map: HashMap<K, V>,
}

impl<K, V> Cache<K, V> {
   // other code
    fn get_or_insert<Q>(&mut self, key: &Q, value: V) -> &mut V
    where
        K: Borrow<Q>,
        Q: ?Sized + Hash + Eq
    {
        todo!()
    }
}
#6

more or less, yes. actually it lacks a value, since it should have the computation "recipe" (closure) at cache creation time, but you got it right.

#7

what are the implications of this to users? and how will a usage of k will look like?

#8

Well, it means that fewer types work for K and Q. Note that Q: ToOwned<Owned = K> is a strictly stronger requirement than K: Borrow<Q> (so you don’t need to write both). It is for example implemented for K == Q and K: Clone, or for K == String and Q == str, or K == Vec<T> and Q == [T] plus T: Clone.

1 Like
#9

Ideally you could use HashMap::raw_entry_mut to do this optimally, but that's on nightly. Fortunately, hashbrown (the crate that backs the std lib's hashmap) does provide this api on stable. hashbrown::HashMap::raw_entry_mut. You can use it like so:

use hashbrown::HashMap;

struct Cache<K, V> {
    map: HashMap<K, V>,
}

impl<K, V> Cache<K, V> {
   // other code
    fn get_or_insert<Q>(&mut self, key: &Q, value: V) -> &mut V
    where
        Q: ?Sized + Hash + Eq + ToOwned<Owned = K>,
    {
        self.map.raw_entry_mut()
            .from_key(key)
            .or_insert_with(move || (key.to_owned(), value))
            .1
    }
}

Otherwise you will have to take a K directly.

2 Likes
#10

Thanks!! I'll give it a shot.