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

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 对可能发生的共享非常严格，因此在这种情况下需要一些额外的努力来说服编译器接受您的代码。

幸运的是，"all the sharing that entails" 并不是字面上的 "all the sharing"：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<...> 是单个不可空指针一样，大概需要在 "do I have a parent or not" 无论如何。)

如果你打算采用这种方法，我建议不要尝试使用 Option 进行部分初始化，而是用它来表示给定集合是 "root" 这一事实.用这种表示很容易向上遍历链，例如

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

同样的方法应该适用于引用，但生命周期通常很难兼顾。

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

Use reference to new struct in the struct initializer

rust