Set of Rc<T> where T isn't Hash or Ord?

user_1043137 0
Viewed 223

Is it possible to have a set of Rc<T>s in Rust (similar to HashSet<Rc<T>>) without T being Hash or Ord?

struct Foo { /* Lots of members, expensive to Hash or Ord */ }

I want to have a set of Rc<Foo> references in a set in order to avoid duplicates. I understand that HashSet<Rc<T>> is expecting T: Hash and BTreeSet<Rc<T>> expects T: Ord:

let mut hash_set = HashSet::<Foo>::new();
hash_set.insert(Foo {}); // error[E0599]: trait bounds were not satisfied

let mut tree_set = BTreeSet::<Foo>::new(); // error[E0277]: trait bound `Foo: Ord` is not satisfied
tree_set.insert(Foo {});

But I don't want to compare by values of Foo objects, I want the set to compare by Rc references. My understanding is that if I change the value of the underlying Foo object, the Rc still points to the same heap address. Therefore that heap address could be used as the basis of hashing or ordering, which is exactly what I want.

Is that possible with Rust's std? Or maybe some crate? Or is my understanding of Rc's incorrect?

rust
1 Answers

You can implement a wrapper for your Rc type. A starting idea would be to use addresses as you suggested. You will need to implement Hash, Eq, and PartialEq.

use std::hash::Hash;

struct Foo {}

struct RcHashFoo(Rc<Foo>);

impl PartialEq for RcHashFoo {
    fn eq(&self, other: &RcHashFoo) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
    }
}

impl Eq for RcHashFoo {}

impl Hash for RcHashFoo {
    fn hash<H>(&self, hasher: &mut H) where H: Hasher { 
        hasher.write_usize(Rc::as_ptr(&self.0) as usize);
    }
}

Playground

user_16951720
Related