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

如何在安全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 回答

?
12345678_0001

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。其他数据结构并保持不变)。第二种限制可以通过使用除借入指针之外的其他东西来存储父对象来缓解。如果想要最大程度的通用性,则可以使用Borrowtrait允许直接值,借用的指针,Boxes,Rc's等。


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


这是我们如何为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 }

    }

}

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


如果上述选项不能令人满意,并且您必须将节点的父级绝对存储在节点中,那么下一个最佳选择是Rc<RefCell<Node<T>>>用来引用父级和子级。Rc启用共享所有权,但增加了在运行时执行引用计数的开销。RefCell启用内部可变性,但增加开销以在运行时跟踪活动借用。有关使用Rc和的实现,请参见DK。的答案RefCell。


查看完整回答
反对 回复 2019-10-21
?
繁花不似锦

问题在于该数据结构本质上是不安全的。它不具有拉斯特不使用直接等同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

添加回答

回复

举报

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