在struct initializer中使用对struct的引用

Question

我想在Rust中创建一个不相交的集合结构。看起来像这样

struct DisjointSet<'s> {
    id: usize,
    parent: &'s mut DisjointSet<'s>,
}

默认的不相交集是单例结构，父表示自身。因此，我希望可以选择执行以下操作：

let a: DisjointSet = DisjointSet {
    id: id,
    parent: self,
};

其中self是对将要创建的对象的引用。

我试过通过创建自定义构造函数来解决这个问题。但是，我的尝试失败了，因为不允许部分初始化。编译器建议使用Option<DisjointSet<'s>>，但这非常难看。你有什么建议吗？

我的问题与Structure containing fields that know each other不同，因为我有兴趣获得对将要创建的结构的引用。

Answer 1

正如@delnan所说，这些数据结构的核心是有向无环图（DAG），所有这些都需要共享。 Rust对于共享可能发生的事情是严格的，因此在这种情况下说服编译器接受您的代码需要花费一些额外的努力。

幸运的是，“所有共享”不是字面上的“所有共享”：DAG是非循环的（模数想要有parent: self），所以像Rc或Arc这样的引用计数类型是处理共享的完美方式（如果有循环，则参考计数不太好）。特别：

struct DisjointSet {
    id: Cell<usize>,
    parent: Rc<DisjointSet>,
}

对于这么小的类型，Cell的运行时开销为零（肯定有一些句法开销）。

不幸的是，由于编译器建议使用Option<...>的原因，这仍然不太正确。没有办法创建第一个DisjointSet。但是，建议的修复仍然有效：

struct DisjointSet {
    id: Cell<usize>,
    parent: Option<Rc<DisjointSet>>,
}

（Option<...>是免费的：Option<Rc<...>>是一个单一的可空指针，就像Rc<...>是一个单独的非可空指针一样，并且可能需要一个分支“无论我是否有父母”。）

如果您打算采用这种方法，我建议不要尝试使用Option进行部分初始化，而是使用它来表示给定集合是“根”的事实。用这种表示很容易遍历链，例如，

fn find_root(mut x: &DisjointSet) -> &DisjointSet {
    while let Some(ref parent) = x.parent {
        x = parent
    }
    x
}

相同的方法应该与引用一起使用，但是生命周期通常很难兼顾。