不再有泪水，不再有结：Rust 中的竞技场分配树

进入竞技场

在使用 Rust 编程时，直接翻译你所熟悉的惯用法并不总是那么简单。其中一类就是树状数据结构。这些结构传统上是由Node引用Node树中其他结构体的结构体构建的。要遍历你的结构体，你需要使用这些引用，而改变树的结构意味着改变每个结构体中引用的节点。

Rust讨厌这种情况。很快你就会遇到问题——例如，在遍历节点时，通常需要借用结构体。借用之后，你再用这个结构体做其他事情就会很麻烦。

不过，树是生活中不可或缺的一部分，而且非常有用。它并不一定有害！我们可以使用基于区域的内存管理来彻底忘掉它。

沙漠

我将简要提及今天尝试此方法之前我曾遇到过的其他几种方法。

最简单的方法是使用unsafe，它允许你像在 C 语言中一样使用原始指针。这会丧失使用安全 Rust 所带来的很多好处，因为一次使用unsafe就会感染你的整个 crate。现在，部分代码之所以被认为是安全的，仅仅是因为你（程序员）认为它是安全的，而不是 Rust 编译器认为它是安全的。

为了坚持静态安全的 Rust，您可以将指针包装在Rc<RefCell<T>>类型中，这些类型是具有内部可变性的引用计数智能指针。当您调用时Rc::clone(&ptr)，您将获得一个指向相同数据的全新指针，该指针可以独立于任何现有指针拥有，并且当所有这样的Rc指针都被删除时，数据本身也会被删除。这是一种静态垃圾收集的形式。RefCell允许您对不可变的东西进行可变借用，并在运行时而不是静态地强制执行。这让您可以作弊，并且panic!()如果搞砸了，所以，我猜是万岁。您需要使用类似但然后可以在遍历期间使用节点的原本不可变的借用来data.borrow_mut()更改字段中的指针。next

或者，你可以使用Box智能指针并克隆它们，这样会毫无意义地执行大量额外工作——这需要深度复制整个子树才能进行细微的编辑。你可以这样做，但这不是我真正喜欢的。

您甚至可以使用简单的引用并引入明确的生命周期：

struct Node<'a> {
    val: i32,
    next: &'a Node,
}

耶，你'a现在可能到处都在撒糖，而且你内心深处有一部分想跟b……搞好关系，然后哇哦。这太恶心了，你正在解决一个简单得多的问题，而这个问题需要……

所有这些选择都意味着痛苦，而且常常需要妥协。至少以我的经验来看，虽然你通常可以成功编译，但你的代码很快就会变得难以阅读和维护，而且如果你需要做出不同的选择，你几乎又回到了原点，试图把所有东西拼凑在一起。这也是我在 Rust 中唯一一次真正导致段错误的情况。我对自己能把事情搞得这么糟感到非常惊讶，我希望自己能更好地记录下是怎么搞砸的，但我知道那只是一些像上面那样的胡言乱语。

问题在于，Rust 会密切关注你的节点所属者以及每个节点的生命周期，但当你构建一个结构体时，编译器并不总是能够轻易理解你正在尝试做什么。最终，你推断出的生命周期对于你的结构体来说太小或不准确，并且无法有效地遍历或编辑映射。你最终需要手动操作来说服编译器你是正确的，这很糟糕。

绿洲

如果你的所有节点都能拥有相同的生命周期会怎么样？我的意思是，它们本质上都是相同的，对吧？当然，有些节点可能会一个接一个地被创建，但就本程序的所有意图和目的而言，你只需要关心它们都归属于你的顶级树结构即可。

有一个超级简单的方法 - 将它们放入Vec<T>：

#[derive(Debug, Default)]
struct ArenaTree<T> 
where
    T: PartialEq
{
    arena: Vec<Node<T>>,
}

轰！树！它对任何能与比较的类型都通用==，生命周期问题也解决了。想要一个节点？那就用吧self.arena[idx]。不用存储对其他节点的实际引用，只需给每个节点一个索引即可：

#[derive(Debug)]
struct Node<T>
where
    T: PartialEq
{
    idx: usize,
    val: T,
    parent: Option<usize>,
    children: Vec<usize>,
}

在这棵树中，每个节点有零个或一个父节点，以及零个或多个子节点。
新节点需要指定 ID 以及要存储的值，并且不会连接到任何其他节点：

impl<T> Node<T>
where
    T: PartialEq
{
    fn new(idx: usize, val: T) -> Self {
        Self {
            idx,
            val,
            parent: None,
            children: vec![],
        }
    }
}

你可以继续存储任意数量的索引——这就是你的图。这只是我在AoC 第 6 天使用的示例树（也是我们在这里的原因）。

这个用法很简单。当你需要某个值时，直接获取它的索引即可：

impl<T> ArenaTree<T>
where
    T: PartialEq
{
    fn node(&mut self, val: T) -> usize {
        //first see if it exists
        for node in &self.arena {
            if node.val == val {
                return node.idx;
            }
        }
        // Otherwise, add new node
        let idx = self.arena.len();
        self.arena.push(Node::new(idx, name));
        idx
    }
}

无论它之前是否存在，现在树中都有该值的索引。如果之前不存在，则会分配一个新节点，该节点与任何现有节点均无连接。当超出ArenaTree范围时，它将自动删除，因此所有节点都将始终与其他节点一样存活，并且所有节点都将同时被清除。

这段代码展示了遍历变得多么简单——你只需使用例如遍历向量即可for node in &self.arena。某些操作变得非常简单——想知道节点数量？直接输入：

fn size(&self) -> usize {
    self.arena.len()
}

那么数一数有多少条边呢？这也不是什么难事，数一数就行了：

fn edges(&self) -> usize {
    self.arena.iter().fold(0, |acc, node| acc + node.children.len())
}

不过，执行标准的递归数据结构操作仍然相当容易。你可以看到一个节点的深度：

fn depth(&self, idx: usize) -> usize {
    match self.arena[idx].parent {
        Some(id) => 1 + self.depth(id),
        None => 0,
    }
}

从根搜索一个值，返回其深度：

fn depth_to_target(&self, idx: usize, target: &T) -> Option<usize> {
    // are we here?  If so, Some(0)
    if target == &self.arena[idx].val {
        return Some(0);
    }

    // If not, try all children
    for p in &self.arena[idx].children {
        if let Some(x) = self.depth_to_target(*p, &target) {
            return Some(1 + x);
        }
    }
    // If it cant be found, return None
    None
}

当然，你也可以迭代遍历。此方法使用迭代和递归遍历来执行一系列深度优先搜索，以查找两个节点的父节点之间的距离：

fn distance_between(&mut self, from: T, target: T) -> usize {
    // If it's not in the tree, this will add a new unconnected node
    // the final function will still return None
    let start_node = self.node(from);
    let mut ret = 0;
    // Start traversal
    let mut trav = &self.arena[start_node];
    // Explore all children, then hop up one
    while let Some(inner) = trav.parent {
        if let Some(x) =  self.depth_to_target(inner, &target) {
            ret += x;
            break;
        }
        trav = &self.arena[inner];
        ret += 1;
    }
    // don't go all the way to target, just orbit
    ret - 1
}

这会在每次回溯时重复一些工作，但即使是谜题规模，计算也几乎是即时的。它非常简洁易读，不像我习惯用来描述 Rust 树的词！

插入将取决于域，但此应用程序接收输入为PARENT)CHILD，所以我的insert看起来像这样：

fn insert(&mut self, orbit: &str) {
    // Init nodes
    let split = orbit.split(')').collect::<Vec<&str>>();
    let inner = self.node(split[0]);
    let outer = self.node(split[1]);
    // set orbit
    match self.object_arena[outer].parent {
        Some(_) => panic!("Attempt to overwrite existing orbit"),
        None => self.object_arena[outer].parent = Some(inner),
    }
    // set parents
    self.object_arena[inner].children.push(outer);
}

总而言之，每当您想要操作给定节点时，您只需要其索引即可。这些都是方便的Copy，所以不必太担心操作它们。要获取节点的索引，请调用tree.node(val)。它总是会成功，通过先执行查找，然后将其分配给树的竞技场（如果它尚不在那里）。然后，您需要将节点的字段操作为其所属的索引：self.arena[idx].children.push(outer);。您永远不需要再担心内存，您的Vec意志会在可能的时候自行放弃。您可以通过每个节点中存储的索引以及插入新索引时发生的情况自己定义树的结构。

基本上，它就像你想要的那样，是一棵树，但它在 Rust 中，你甚至不必为它而争斗，这很棒。

这是一个可供戳戳和戳戳的游乐场链接。

封面图片由 Amanda Flavell 在 Unsplash 上提供

鏂囩珷鏉ユ簮锛�https://dev.to/decidously/no-more-tears-no-more-knots-arena-allocated-trees-in-rust-44k6