Let's say I have to store the cost of traversal between nodes in a non directed graph. I'd like to have a HashMap that uses pairs of String or &str as keys and u32 as values. Is there a data container that can be used as key such that map.get(container("a","b")) == map.get(container("b", "a"))?
- How could this question be improved?none none– none none2022-02-28 17:17:59 +00:00Commented Feb 28, 2022 at 17:17
Add a comment |
2 Answers
Building on what at54321 said, you can implement an "unordered pair" type that enforces a consistent order, effectively making (a, b) and (b, a) equal values. Using this as the map's key type will prevent any possibility of accidentally looking up a pair with the larger value first.
This means that ref_a() may not return the first value passed to the constructor. This type implements From<(T, T)>, so if ordering is needed in other parts of the application you can continue to use a tuple and use .into() when interacting with a map.
use std::cmp::Ordering; use std::hash::{Hash, Hasher}; struct UnorderedPair<T> { a: T, b: T, } impl<T: Ord> UnorderedPair<T> { pub fn new(a: T, b: T) -> Self { if a < b { Self { a, b } } else { Self { a: b, b: a } } } pub fn ref_a(&self) -> &T { &self.a } pub fn ref_b(&self) -> &T { &self.b } } impl<T: Ord> From<(T, T)> for UnorderedPair<T> { fn from(t: (T, T)) -> Self { Self::new(t.0, t.1) } } impl<T: PartialEq<T>> PartialEq<UnorderedPair<T>> for UnorderedPair<T> { fn eq(&self, rhs: &Self) -> bool { self.a == rhs.a && self.b == rhs.b } } impl<T: Eq> Eq for UnorderedPair<T> { } impl<T: PartialOrd> PartialOrd for UnorderedPair<T> { fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> { match self.a.partial_cmp(&rhs.a) { Some(Ordering::Equal) => self.b.partial_cmp(&rhs.b), v => v, } } } impl<T: Ord> Ord for UnorderedPair<T> { fn cmp(&self, rhs: &Self) -> std::cmp::Ordering { match self.a.cmp(&rhs.a) { Ordering::Equal => self.b.cmp(&rhs.b), v => v, } } } impl<T: Hash> Hash for UnorderedPair<T> { fn hash<H: Hasher>(&self, hasher: &mut H) { self.a.hash(hasher); self.b.hash(hasher); } } Then, for example:
use std::collections::HashMap; fn main() { let mut map = HashMap::new(); map.insert(UnorderedPair::new("a", "b"), "c"); assert_eq!(map.get(&("a", "b").into()), Some(&"c")); assert_eq!(map.get(&("b", "a").into()), Some(&"c")); assert_eq!(map.get(&("a", "a").into()), None); } 
16 Comments
Peter Hall
The implementation of
PartialEq must be consistent with the Hash impl. So you need to change it to: self.a == rhs.a && self.b == rhs.b || self.a == rhs.b && self.b == rhs.a.Peter Hall
And, for that reason, I don't think you can implement
Ord for UnorderedPair (because Ord and Eq must also be consistent or else you will break BTrees).
cdhowie
@PeterHall I'm not sure how that could be violated in my implementation as
a and b are forced into an order in new(). self.a <= self.b is an invariant of this type. ... Except that mutation is possible -- I need to remove the mut accessors. Edit: Mut accessors are gone.
canton7
I think I'd find it more intuitive if your type kept the order of
a and b the same, but Eq and Hash were implemented such that the order didn't matter. Your wrapper could even be a newtype.
Locke
@cdhowie, I took your playground example and made a version with what I would consider a truly unordered pair which maintains the position of each item without ordering any guarantees. However, it does have the downside of needing to determine an ordering whenever it needs to perform an action. playground link.
|
In such cases I think it's usually best to simply use a consistent order of the strings in the pair. Let's say you have a tuple (s1, s2). If you always put the smaller string first, then everything will work as expected. Example: ("foo", "bar") and ("bar", "foo") will always be represented the same way, as ("bar", "foo").
You can implement a custom container type that does that for you or you can simply have a helper function like this:
fn as_key<'a>(s1: &'a str, s2: &'a str) -> (&'a str, &'a str) { if s1 < s2 { (s1, s2) } else { (s2, s1) } } fn main() { println!("{:?}", as_key("foo", "bar")); // Prints ("bar", "foo") println!("{:?}", as_key("bar", "foo")); // Prints ("bar", "foo") } If you only have a few places where you work with the map, using a helper function like the above as_key will probably be the simplest solution, but you mustn't forget to call it each time you need to pass a key to the map. Using a custom type would require a bit more code, but it would be safer.
