Here’s a prototype of an extension of what HashMap::get is using Borrow for.
What Problem does it Solve?
You have a hash table with key type (String, String) and you want to do a table lookup without allocating strings. It allows lookup not using a custom type like Pair(&str, &str) (or even using the (&str, &str) tuple if libstd buys into it).
Implementation
Two things are needed: The substitute key (Q) must be hashable (like the K type), and there must be a K to Q equality function (a function to avoid the limitations of Borrow).
/// Key lookup trait.
///
/// This trait allows hash table lookup to be customized.
/// It has one blanket implementation that uses the regular `Borrow` solution,
/// just like `HashMap` and `BTreeMap` do, so that you can pass `&str` to lookup
/// into a map with `String` keys and so on.
///
/// # Contract
///
/// The implementor must hash like `K`.
pub trait Lookup<K: ?Sized> : Hash {
/// Compare self to `key` and return `true` if they are equal.
fn equal(&self, key: &K) -> bool;
}
impl<Q: ?Sized, K: ?Sized> Lookup<K> for Q
where Q: Eq + Hash,
K: Borrow<Q>,
{
fn equal(&self, key: &K) -> bool {
*self == *key.borrow()
}
}
I ran into this exact issue the other day. Frustrating not being able to avoid the allocation, despite all the care that goes into avoiding double lookups. Big plus one for this from me
Related: It would also be great to extend the entry API to take a type L where L: ToOwned<Key>, Key: Borrow<L> rather than a Key directly so that if the key is already in the map, we can avoid an unnecessary allocation.
I had something like this in mind, which allows a key to be extracted from any type. This allows you to place bounds (such as Eq + Hash for HashMap and Ord for BTreeMap) directly on the key type, and keeps the key extraction mechanism independent of any particular collection type.
This example code makes use of associated type constructors and specialization, but it could be made to work without those features.
pub trait ExtractKey {
type Key<'a>;
fn extract_key(&self) -> Self::Key;
}
// Default implementation which just returns self
impl<T> ExtractKey for T {
default type Key<'a> = &'a T;
default fn extract_key(&self) -> &T {
self
}
}
struct Example(String, i32, f64);
impl ExtractKey for Example {
// Since Key is generic over lifetimes, we can return fields in an
// arbitrary order, which can be used to control BTreeMap ordering.
type Key<'a> = (f64, &'a str);
fn extract_key(&self) -> (&'a str, f64) {
(self.2, &self.0)
}
}
I have a partial implementation of this for HashMap/BTreeMap, although it’s named differently (I didn’t see this thread until I was done). Patch at https://github.com/rust-lang/rust/commit/e3ec035c338927f277ca7d4509587185e6cac1f1 - not sure about the type or method names, and it needs a few more added (the Range ops on BTree, for one).
