data-structures - 如何在安全Rust中表达相互递归的数据结构？

我正在尝试在Rust中实现类似于场景图的数据结构。我想要一个等效于用安全Rust表示的C++代码:

struct Node
{
    Node* parent; // should be mutable, and nullable (no parent)
    std::vector<Node*> child;

    virtual ~Node()
    {
        for(auto it = child.begin(); it != child.end(); ++it)
        {
            delete *it;
        }
    }

    void addNode(Node* newNode)
    {
        if (newNode->parent)
        {
            newNode->parent.child.erase(newNode->parent.child.find(newNode));
        }
        newNode->parent = this;
        child.push_back(newNode);
    }
}

我想要的属性:

父级拥有其子级的所有权

可以通过某种

的引用从外部访问节点
碰到一个Node的

事件可能会使整个树

发生变异

最佳答案

Rust试图通过禁止您执行可能不安全的操作来确保内存安全。由于此分析是在编译时执行的，因此编译器只能推理已知安全的操作子集。

在Rust中，您可以轻松地存储对父级的引用(通过借用父级，从而防止突变)或子级节点列表(通过拥有它们，这将为您提供更多的自由度)，但不能同时存储两者(不使用unsafe)。这对于addNode的实现尤其成问题，它需要对给定节点的父级进行可变访问。但是，如果将parent指针存储为可变引用，则由于一次只能使用对特定对象的单个可变引用，因此访问父级的唯一方法是通过子节点，并且只能有一个子节点，否则您将有两个对同一个父节点的可变引用。

如果要避免使用不安全的代码，可以有很多选择，但是它们都需要做出一些牺牲。

最简单的解决方案是仅删除parent字段。我们可以定义一个单独的数据结构，以在遍历树时记住节点的父节点，而不是将其存储在节点本身中。

首先，让我们定义Node:

#[derive(Debug)]
struct Node<T> {
    data: T,
    children: Vec<Node<T>>,
}

impl<T> Node<T> {
    fn new(data: T) -> Node<T> {
        Node { data: data, children: vec![] }
    }

    fn add_child(&mut self, child: Node<T>) {
        self.children.push(child);
    }
}

(我添加了一个data字段，因为如果在节点上没有数据，树就没有多用!)

现在让我们定义另一个结构，以在导航时跟踪父级:

#[derive(Debug)]
struct NavigableNode<'a, T: 'a> {
    node: &'a Node<T>,
    parent: Option<&'a NavigableNode<'a, T>>,
}

impl<'a, T> NavigableNode<'a, T> {
    fn child(&self, index: usize) -> NavigableNode<T> {
        NavigableNode {
            node: &self.node.children[index],
            parent: Some(self)
        }
    }
}

impl<T> Node<T> {
    fn navigate<'a>(&'a self) -> NavigableNode<T> {
        NavigableNode { node: self, parent: None }
    }
}

如果您不需要在导航树时对其进行突变，并且可以保留父NavigableNode对象(对于递归算法而言效果很好，但如果要存储NavigableNode，效果就不太好)，则此解决方案效果很好并保留在其他数据结构中)。第二种限制可以通过使用除借入指针之外的其他东西来存储父对象来缓解。如果想要最大程度的通用性，则可以使用 Borrow trait来允许直接值，借用的指针，Box es，Rc等等。

现在，让我们谈谈zippers。在函数式编程中， zipper 用于“关注”数据结构的特定元素(列表，树， map 等)，以便访问该元素需要花费恒定的时间，同时仍保留该数据结构的所有数据。如果您需要导航树并在导航过程中将更改为，同时保留向上导航树的功能，则可以将树变成 zipper 并通过 zipper 执行修改。

这是我们如何为上面定义的Node实现 zipper 的方法:

#[derive(Debug)]
struct NodeZipper<T> {
    node: Node<T>,
    parent: Option<Box<NodeZipper<T>>>,
    index_in_parent: usize,
}

impl<T> NodeZipper<T> {
    fn child(mut self, index: usize) -> NodeZipper<T> {
        // Remove the specified child from the node's children.
        // A NodeZipper shouldn't let its users inspect its parent,
        // since we mutate the parents
        // to move the focused nodes out of their list of children.
        // We use swap_remove() for efficiency.
        let child = self.node.children.swap_remove(index);

        // Return a new NodeZipper focused on the specified child.
        NodeZipper {
            node: child,
            parent: Some(Box::new(self)),
            index_in_parent: index,
        }
    }

    fn parent(self) -> NodeZipper<T> {
        // Destructure this NodeZipper
        let NodeZipper { node, parent, index_in_parent } = self;

        // Destructure the parent NodeZipper
        let NodeZipper {
            node: mut parent_node,
            parent: parent_parent,
            index_in_parent: parent_index_in_parent,
        } = *parent.unwrap();

        // Insert the node of this NodeZipper back in its parent.
        // Since we used swap_remove() to remove the child,
        // we need to do the opposite of that.
        parent_node.children.push(node);
        let len = parent_node.children.len();
        parent_node.children.swap(index_in_parent, len - 1);

        // Return a new NodeZipper focused on the parent.
        NodeZipper {
            node: parent_node,
            parent: parent_parent,
            index_in_parent: parent_index_in_parent,
        }
    }

    fn finish(mut self) -> Node<T> {
        while let Some(_) = self.parent {
            self = self.parent();
        }

        self.node
    }
}

impl<T> Node<T> {
    fn zipper(self) -> NodeZipper<T> {
        NodeZipper { node: self, parent: None, index_in_parent: 0 }
    }
}

要使用此 zipper ，您需要拥有树的根节点的所有权。通过获得节点的所有权， zipper 可以四处移动，以避免复制或克隆节点。当我们移动一个 zipper 时，我们实际上放下了旧的 zipper 并创建了一个新的 zipper (尽管我们也可以通过对self进行突变来做到这一点，但我认为这样更清晰，而且它还允许您链接方法调用)。

如果上述选项不能令人满意，并且必须将节点的父级绝对存储在节点中，那么下一个最佳选择是使用Rc<RefCell<Node<T>>>引用父级，并使用Weak<RefCell<Node<T>>>引用子级。 Rc 启用共享所有权，但增加了开销，以便在运行时执行引用计数。 RefCell 启用内部可变性，但增加开销以在运行时跟踪 Activity 借用。 Weak 类似于Rc，但不会增加引用计数；这用于中断引用周期，这将防止引用计数下降到零，从而导致内存泄漏。 See DK.'s answer用于使用Rc，Weak和RefCell的实现。