在结构初始值设定项中使用对新结构的引用

Question

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

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

默认的不交集集是单例结构，其中父级引用自身。因此，我想选择执行以下操作：

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

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

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

我的问题不同于包含彼此认识的字段的结构， 因为我有兴趣获取对将要创建的结构的引用。

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
}

相同的方法应该可以很好地与引用配合使用，但是生命周期通常很难兼顾。