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

Question

我正在尝试在 Rust 中实现类似场景图的数据结构。我想要一个用 safe 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);
    }
}

我想要的属性:

• parent 拥有 child 的所有权
• 节点可以通过某种引用从外部访问
• 触及一个节点的事件可能会改变整棵树

Answer 1

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

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

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

---

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

首先，让我们定义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是的，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 并创建一个新的(虽然我们也可以通过改变 self 来做到这一点，但我认为这样更清楚，而且它可以让你链接方法调用)。

---

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