I have become dimly aware of an issue in the standard library maps ( HashMap, BTreeMap etc. ) which I don't entirely understand, but I think this crate solves:
Also, HashBrown seems to have [it's own version - Edit: nope, it is using the crate] of Equivalent but not Comparable. Anyway, I was thinking of updating my pstd crate (which has BTreeMap etc implementations) to use this, but wondered if there is any downside before I go ahead.
I think I came across an example of this myself, I wanted to make a HashMap where the key is (u64, String), but it seems awkward without doing extra cloning operations or something when you want to use get. I gave up and did it another way.
I found here : The Rust Data Structure Handbook: Theoretical Insights and Practical Techniques for Mastery on amazon i don't sure if it is free totally or not but cheap at 6.07$ on Kindle.
Hope that help you for data structure 
Enjoy !
The issue that equivalent solves is the classic “std only supports &'varying T lifetime-infected families of types, not a general T<'varying> family.”
In this case, std collections use Borrow to compare a key in the collection against a borrowed version of that key, and you can’t borrow a (u64, String) into a (&u64, &str) or similar, since the latter is not of the form &T for some T.
Granted... equivalent still uses &K… so there ends up being an extra layer of indirection, like &(u64, &str) instead of (u64, &str) or similar. I guess the idea is that the trait is still more flexible than using Borrow and PartialEq, even with that limitation, since you don’t have to produce such a reference from the owned key. Presumably references are used for the sake of simplicity (a proper solution requires for<'varying> binders and implied bounds), but it seems slightly unfortunate.
To try and get my head around it, I made a little example:
use hashbrown::{Equivalent,HashMap};
#[derive(Hash)]
struct Key<'a>{
x: u64,
s: &'a str
}
impl <'a> Equivalent<(u64,String)> for Key<'a>
{
fn equivalent(&self, k: &(u64, String)) -> bool {
self.x == k.0 && self.s == k.1
}
}
fn main()
{
let mut m = HashMap::<(u64,String), u64>::default();
m.insert( (99, String::from("hello")), 98 );
println!("m={:?}", m);
let x = m.get( &Key{x:99,s:"hello"} );
println!("x={:?}", x);
}
Is that how this is supposed to work? Is there a better way?
Interesting, I confused what hashbrown uses Self and K for. (Since the method arguments are of types &Self and &K, what I said still applies after interchanging the two.)
Anyway, yes, that looks like what I expected. If there’s a better way to use equivalent, I don’t know it.
I managed to update pstd, the main functions seem fine, but I think there are some type inference compatibility issues with for example range. I had test failures, e.g.
error[E0283]: type annotations needed
--> src/collections/btree_set/tests.rs:626:11
|
626 | v.range(..)
| ^^^^^ cannot infer type of the type parameter `Q` declared on the method `range`
|
= note: the type must implement `Comparable<T>`
note: required by a bound in `BTreeSetA::<T, A>::range`
--> src/collections/btree_set.rs:713:12
|
711 | pub fn range<Q, R>(&self, range: R) -> Range<'_, T>
| ----- required by a bound in this associated function
712 | where
713 | Q: Comparable<T> + ?Sized + Ord,
| ^^^^^^^^^^^^^ required by this bound in `BTreeSetA::<T, A>::range`
help: consider specifying the generic arguments
|
626 | v.range::<Q, RangeFull>(..)
| ++++++++++++++++
I think there might be similar problems with BTreeMap range but it isn't caught by the tests (edit: it is, but I wasn't running the applicable tests). I saw them internally, and managed (with difficulty) to work around them internally, but this seems to be an issue. I haven't tried to fix the tests yet ( maybe that would be cheating... ). I think it is unbounded ranges that are the problem.
What if you make your own ComparableRangeBounds<K> trait? Something like
trait ComparableRangeBounds<K>: RangeBounds<Self::Q> {
type Q: Equivalent<K> + Ord + ?Sized;
}
impl<K: Ord, Q: Equivalent<K> + Ord + ?Sized> ComparableRangeBounds<K> for /* each range type over `Q` except `RangeFull` */ {
type Q = Q;
}
impl<K: Ord> ComparableRangeBounds<K> for RangeFull {
// RangeFull does not contain any Q values, so this type doesn’t really matter
type Q = K;
}
Oh, “EquivalentRangeBounds” would be the better name.
I made a simple test to show it can work with type annotations:
use super::*;
#[derive(Eq,PartialEq,Ord,PartialOrd)]
struct Key<'a>{
x: u64,
s: &'a str
}
impl <'a> Comparable<(u64,String)> for Key<'a>
{
fn compare(&self, k: &(u64, String)) -> Ordering {
let o = self.x.compare(&k.0);
if o != Ordering::Equal { return o; }
self.s.compare(&k.1)
}
}
impl <'a> Equivalent<(u64,String)> for Key<'a>
{
fn equivalent(&self, k: &(u64, String)) -> bool {
self.x == k.0 && self.s == k.1
}
}
#[test]
fn test_comparable() {
let mut m = BTreeMap::<(u64,String), u64>::new();
m.insert( (99, String::from("hello")), 98 );
m.insert( (99, String::from("george")), 98 );
println!("m={:?}", m);
let x = m.get( &Key{x:99,s:"hello"} );
println!("x={:?}", x);
let start = &Key{x:99,s:"aaa"};
let end = &Key{x:100,s:"hello"};
for (k,v) in m.range::<Key,_>( start..end )
{
println!("k={:?} v={:?}", k, v );
}
}
This inference failure is the same thing that I commented on the tracking issue, citing my other comment on indexmap, whereas flipping it like K: Comparable<Q> does work.
Well in the end I fixed up the tests where new type annotations were needed ( and also there were a few mistakes I made in the general struggle to get it to work ). So I think it is job done everything seems neat and working, albeit it is unfortunate that in a few cases extra type annotations are required ( I cannot say I fully understand why, type inference is always a bit of a mystery to me! ).
Oh, so maybe I should go the other way. Maybe I will try that tomorrow, right now I need a rest.
Note that you'll need to define your own traits though, since the equivalent crate has the blanket impls going the original direction for Borrow and Eq/Ord.