拥有的arena数据结构

Question

我想对由许多非常大（内存方面）的节点组成的非常大（节点数）的图建模。由于节点太大，我只想存储它们一次并向它们传递借用，所以从概念上讲是这样的：

struct Graph<'a> {
    nodes: Vec<Node<'a>>,
}

struct Node<'a> {
    edges: HashMap<String, &'a Node>,
    // ...lots of other data...
}

当然没有办法像这样构造一个Graph因为（a）Vec不允许我在元素借用时添加新节点，并且（b）我不能告诉 rustc nodes 向量将存在一生 'a。我也不能使用像 Rc 这样的东西，因为图形有循环。

我希望能够表达的是一种竞技场，它让我可以分配很多 Node，只要竞技场存在，就向它们进行不可变借用，并使用生命周期检查以确保在取消分配竞技场时我没有剩余的 Node 引用。类似于：

struct Graph<'a> {
    nodes: Arena<'a, Node<'a>>,
}

struct Node<'a> {
    edges: HashMap<String, &'a Node>,
}

impl<'a, A> Arena<'a, A> {
    fn own(&self, a: A) -> &'a A {
        // magic
    }
}

impl<'a, A> Drop for Arena<'a, A> {
    fn drop(&'a mut self) {
        // magic
    }
}

这在语义上可以用 Rust 表达吗？

Answer 1

一个简单的首选解决方案是使用 typed-arena 箱子。它包含一个 Arena 类型和一个 fn alloc(&self, T) -> &mut T 方法。

另一个简单的解决方案是使用索引而不是引用（永远不要从 Vec 中删除，因为这会使索引无效）。在 64 位平台上，使用 32 位索引可以减少一些字节。

但是，这两种解决方案都无法删除节点。您可以停止引用它们，但它们仍将存在于内存中，因此将它们用于动态图（节点来来去去）需要更多的工作。在这种情况下，我的建议是定期从一个新的领域创建一个新的图形克隆（而不是复制未使用的节点），这类似于使用移动垃圾收集器，如果不那么自动的话。

拥有的arena数据结构

Owned arena data structure

graph

rust

lifetime

ownership