为了账号安全,请及时绑定邮箱和手机立即绑定

如何在安全Rust中表达相互递归的数据结构?

/ 猿问

如何在安全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可能会改变整个树


查看完整描述

3 回答

?
繁花不似锦

问题在于该数据结构本质上是不安全的。它不具有拉斯特不使用直接等同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,以确保给定的节点不会意外留下错误的父级的子级。


这并不是严格地优于第二种选择,因为这种设计绝对不能从静态借阅检查中受益。第二种方法至少可以防止您在编译时一次从两个地方更改图形;在这里,如果发生这种情况,您将崩溃。


关键是:您不能拥有一切。您必须确定您实际需要支持的操作。那时,通常只是选择为您提供必要属性的类型的一种情况。


查看完整回答
反对 回复 2019-10-21
?
偶然的你

在某些情况下,您也可以使用arena。竞技场保证存储在其中的值与竞技场本身具有相同的生存期。这意味着添加更多的值不会使任何现有生命周期无效,但会移动竞技场。因此,如果您需要返回树,则这种解决方案是不可行的。


通过从节点本身删除所有权来解决此问题。


这是一个示例,该示例还使用内部可变性来允许节点在创建后进行突变。在其他情况下,如果仅构造树然后简单地对其进行导航,则可以删除此可变性。


extern crate typed_arena; // 1.4.1


use std::{cell::{Cell, RefCell}, fmt};

use typed_arena::Arena;


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 (), )

}


查看完整回答
反对 回复 2019-10-21
  • 3 回答
  • 0 关注
  • 236 浏览
我要回答

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信