Rust： Set of Sets

发布于03月22日

一个人如何创造出一套铁 rust ？是否有必要为满足HashSet<HashSet<_>>的每种混凝土类型写一个impl块？

最简单的失败例子:

fn main () {
    let a: HashSet<u32> = HashSet::new();
    let c: HashSet<HashSet<u32>> = HashSet::new();
    c.insert(a);
}

错误:

"insert" method cannot be called on `std::collections::HashSet<std::collections::HashSet<u32>>` due to unsatisfied trait bounds
HashSet doesn't satisfy `std::collections::HashSet<u32>: Hash

有没有可能推翻哈塞特不幸的事实？我想使用散列集，需要我的内容通过实际(内存)相等来唯一；我不需要根据内容来区分.

推荐答案

我希望有一组集合，并希望它们通过"实际"(内存)相等而不是内容来唯一.

为此，首先需要对哈希集进行装箱，使其具有稳定的内存地址.例如:

struct Set<T>(Box<HashSet<T>>);

要使Set可散列，需要实现Hash和Eq:

impl<T> Set<T> {
    fn as_addr(&self) -> usize {
        // as_ref() gives the reference to the heap-allocated contents
        // inside the Box, which is stable; convert that reference to a
        // pointer and then to usize, and use it for hashing and equality.
        self.0.as_ref() as *const _ as usize
    }
}

impl<T> Hash for Set<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.as_addr().hash(state);
    }
}

impl<T> Eq for Set<T> {}

impl<T> PartialEq for Set<T> {
    fn eq(&self, other: &Self) -> bool {
        self.as_addr() == other.as_addr()
    }
}

最后，需要添加一些类似集合的方法和构造函数以使其可用:

impl<T: Hash + Eq> Set<T> {
    pub fn new() -> Self {
        Set(Box::new(HashSet::new()))
    }

    pub fn insert(&mut self, value: T) {
        self.0.insert(value);
    }

    pub fn contains(&mut self, value: &T) -> bool {
        self.0.contains(value)
    }
}

现在，您的代码将正常工作，并额外使用Rc，这样您就可以在插入原始Set后进行查找:

fn main() {
    let mut a: Set<u32> = Set::new();
    a.insert(1);
    let a = Rc::new(a);
    let mut c: HashSet<_> = HashSet::new();
    c.insert(Rc::clone(&a));
    assert!(c.contains(&a));
}

Playground