If the keys of my HashMap are String, I can query the HashMap using a &str because String implements Borrow<str>. This allows me to avoid allocating a new String for every get.
How can I avoid allocating when my key is an Option<String>, which can't implement Borrow<str> because of the None case?
use std::collections::HashMap;
fn main() {
let mut map: HashMap<Option<String>, usize> = HashMap::new();
map.insert(Some("foo".to_string()), 100);
map.insert(Some("bar".to_string()), 200);
map.insert(Some("baz".to_string()), 300);
// How can I run this query without allocating?
let value = map.get("foo").unwrap();
}
The solutions of which I'm aware are:
Use a library like indexmap that provides its own equivalence/querying trait that's easier to satisfy.
Make a wrapper for Option<String> that implements Borrow<&dyn SomeTrait> that gives me more flexibility.
I'm interested to know if there's a way to achieve this that avoids a new dependency and/or dynamic dispatch.
You could make a key wrapper for Option<String> that implements Borrow<Option<&str>>, and then lookups can use .get(&Some("foo")) -- a little clunky, but still not allocating.
(edit: nevermind, there's no way to tie the lifetime in that Option<&str>...)
Instead of HashMap<Option<String>, T>, you can have (HashMap<String, T>, Option<T>) or similar struct where the second field represent the entry for the None key.
I can't help but wonder if there's a way to make Borrow<T> (and/or HashMap) more flexible for this sort of use case. Borrow's requirement that the output value have the same lifetime as &self seems unnecessarily restrictive. The fact that indexmap was able to work around this with a custom trait (and a blanket impl for T: Borrow) seems to suggest it's possible.
Or perhaps now that GATs are landing the Borrow trait could (someday) leverage that and specify a default lifetime?
It isn't. Without this requirement, Borrow couldn't be usefully implemented for owning types. (If you borrow a String, where should the output lifetime come from, it not from &self?)
The Equivalent trait you are referring to doesn't substitute Borrow, it's more like a more general version of PartialEq.
In the context of maps, it's a substitute for both. The standard library uses K: Borrow<Q>, Q: Hash + Eq, while indexmap uses only Q: Hash + Equivalent<K>. There's a blanket impl that makes it behave the same way for types that do borrow, but you can also impl Equivalent separately for your own Q and K without any borrowing (as long as that doesn't overlap).
