我正在尝试在 Rust 中实现类似场景图的数据结构。我想要一个等效于这个C++代码，用安全的 Rust 表达：
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 特征来允许直接值、借用指针、Box ES、Rc 等。
现在，让我们谈谈拉链。在函数式编程中，拉链用于"关注"数据结构的特定元素（列表、树、映射等），以便访问该元素需要恒定的时间，同时仍保留该数据结构的所有数据。如果您需要导航树并在导航过程中对其进行更改，同时保留向上导航树的能力，则可以将树变成拉链并通过拉链执行修改。
以下是我们如何为上面定义的Node实现拉链：
#[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 }
}
}
要使用此拉链，您需要拥有树的根节点的所有权。通过获得节点的所有权，拉链可以移动东西，以避免复制或克隆节点。当我们移动拉链时，我们实际上放下旧拉链并创建一个新拉链（虽然我们也可以通过改变self来做到这一点，但我认为这样更清晰，而且它可以让您链接方法调用）。
如果上述选项不令人满意，并且必须将节点的父节点绝对存储在节点中，那么下一个最佳选择是使用 Rc<RefCell<Node<T>>> 来引用父节点，Weak<RefCell<Node<T>>>引用子节点。 Rc启用共享所有权，但会增加在运行时执行引用计数的开销。 RefCell 支持内部可变性，但增加了开销以在运行时跟踪活动借用。 Weak 类似于 Rc ，但它不会增加引用计数;这用于中断引用周期，这将防止引用计数降至零，从而导致内存泄漏。请参阅DK关于使用Rc、Weak和RefCell实现的答案。
问题是这种数据结构本质上是不安全的; 它在 Rust 中没有不使用unsafe的直接等价物。 这是设计使然。
如果你想把它翻译成安全的 Rust 代码，你需要更具体地说明你想要从中得到什么。 我知道你在上面列出了一些属性，但经常来到 Rust 的人会说"我想要这个 C/C++ 代码中的所有东西"，直接回答是"好吧，你不能"。
你也不可避免地将不得不改变你处理这个问题的方式。 您给出的示例具有没有任何所有权语义、可变别名和循环的指针;所有这些都 Rust 不允许你像C++那样简单地忽略。
最简单的解决方案是摆脱parent指针，并在外部维护它（如文件系统路径）。 这也与借款配合得很好，因为任何地方都没有周期：
pub struct Node1 {
children: Vec<Node1>,
}
如果你需要父指针，你可以半途而废，改用 Ids：
use std::collections::BTreeMap;
type Id = usize;
pub struct Tree {
descendants: BTreeMap<Id, Node2>,
root: Option<Id>,
}
pub struct Node2 {
parent: Id,
children: Vec<Id>,
}
BTreeMap实际上是您的"地址空间"，通过不直接使用内存地址来绕过借用和混叠问题。
当然，这引入了给定Id未绑定到特定树的问题，这意味着它所属的节点可能会被破坏，现在您实际上是一个悬空指针。 但是，这就是你为混叠和突变付出的代价。 它也不太直接。
或者，你可以全猪，使用引用计数和动态借用检查：
use std::cell::RefCell;
use std::rc::{Rc, Weak};
// Note: do not derive Clone to make this move-only.
pub struct Node3(Rc<RefCell<Node3_>>);
pub type WeakNode3 = Weak<RefCell<Node3>>;
pub struct Node3_ {
parent: Option<WeakNode3>,
children: Vec<Node3>,
}
impl Node3 {
pub fn add(&self, node: Node3) {
// No need to remove from old parent; move semantics mean that must have
// already been done.
(node.0).borrow_mut().parent = Some(Rc::downgrade(&self.0));
self.children.push(node);
}
}
在这里，您将使用 Node3 在树的各个部分之间转移节点的所有权，并WeakNode3外部引用。 或者，您可以使Node3可克隆，并重新添加add中的逻辑，以确保给定节点不会意外地保持错误父节点的子节点。
严格来说，这并不比第二种选择更好，因为这种设计绝对不能从静态借用检查中受益。 第二个至少可以防止你在编译时同时从两个地方改变图形;在这里，如果发生这种情况，你只会崩溃。
关键是：你不能什么都拥有。 您必须决定实际需要支持哪些操作。 此时，通常只需选择为您提供必要属性的类型即可。
在某些情况下，您还可以使用竞技场。竞技场保证存储在其中的值与竞技场本身具有相同的生存期。这意味着添加更多值不会使任何现有生存期失效，但移动竞技场会失效。因此，如果您需要返回树，这样的解决方案是不可行的。
这通过删除节点本身的所有权来解决问题。
下面是一个示例，该示例还使用内部可变性来允许节点在创建后发生突变。在其他情况下，如果树被构造一次，然后简单地导航，则可以删除此可变性。
use std::{
cell::{Cell, RefCell},
fmt,
};
use typed_arena::Arena; // 1.6.1
struct Tree<'a, T: 'a> {
nodes: Arena<Node<'a, T>>,
}
impl<'a, T> Tree<'a, T> {
fn new() -> Tree<'a, T> {
Self {
nodes: Arena::new(),
}
}
fn new_node(&'a self, data: T) -> &'a mut Node<'a, T> {
self.nodes.alloc(Node {
data,
tree: self,
parent: Cell::new(None),
children: RefCell::new(Vec::new()),
})
}
}
struct Node<'a, T: 'a> {
data: T,
tree: &'a Tree<'a, T>,
parent: Cell<Option<&'a Node<'a, T>>>,
children: RefCell<Vec<&'a Node<'a, T>>>,
}
impl<'a, T> Node<'a, T> {
fn add_node(&'a self, data: T) -> &'a Node<'a, T> {
let child = self.tree.new_node(data);
child.parent.set(Some(self));
self.children.borrow_mut().push(child);
child
}
}
impl<'a, T> fmt::Debug for Node<'a, T>
where
T: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{:?}", self.data)?;
write!(f, " (")?;
for c in self.children.borrow().iter() {
write!(f, "{:?}, ", c)?;
}
write!(f, ")")
}
}
fn main() {
let tree = Tree::new();
let head = tree.new_node(1);
let _left = head.add_node(2);
let _right = head.add_node(3);
println!("{:?}", head); // 1 (2 (), 3 (), )
}
TL;DR：DK. 的第二个版本无法编译，因为 parent 有 self.0 以外的其他类型，请通过将其转换为弱节点来修复它。此外，在下面的行中，"self"没有"child"属性，但self.0有。
<小时 />我更正了DK的版本，因此它可以编译和工作。这是我的代码：
dk_tree.rs
use std::cell::RefCell;
use std::rc::{Rc, Weak};
// Note: do not derive Clone to make this move-only.
pub struct Node(Rc<RefCell<Node_>>);
pub struct WeakNode(Weak<RefCell<Node_>>);
struct Node_ {
parent: Option<WeakNode>,
children: Vec<Node>,
}
impl Node {
pub fn new() -> Self {
Node(Rc::new(RefCell::new(Node_ {
parent: None,
children: Vec::new(),
})))
}
pub fn add(&self, node: Node) {
// No need to remove from old parent; move semantics mean that must have
// already been done.
node.0.borrow_mut().parent = Some(WeakNode(Rc::downgrade(&self.0)));
self.0.borrow_mut().children.push(node);
}
// just to have something visually printed
pub fn to_str(&self) -> String {
let mut result_string = "[".to_string();
for child in self.0.borrow().children.iter() {
result_string.push_str(&format!("{},", child.to_str()));
}
result_string += "]";
result_string
}
}
然后是 main.rs 中的主函数：
mod dk_tree;
use crate::dk_tree::{Node};
fn main() {
let root = Node::new();
root.add(Node::new());
root.add(Node::new());
let inner_child = Node::new();
inner_child.add(Node::new());
inner_child.add(Node::new());
root.add(inner_child);
let result = root.to_str();
println!("{result:?}");
}
我让弱节点更像节点的原因是，两者之间的转换更容易