如何建模复杂的递归数据结构（图形）？

Question

我对 Rust 非常感兴趣，现在正在开始我的第一个语言项目。我仍然无法完全理解借用和生命周期的概念。

该应用程序是一个逻辑门模拟器，其中的组件是递归定义的（根据其他组件及其互连）。

我目前的计划是像在 C++ 中那样实现这一点，方法是让一个组件结构拥有一个组件向量（它的子组件）和一个描述这些组件之间相互连接的网络向量：

pub struct Pin {
    name: String
}

pub struct Net<'a> {
    nodes: Vec<(&'a Component<'a>,&'a Pin)>
}

pub struct Component<'a> {
    sub_components: Vec<Box<Component<'a>>>,
    in_pins: Vec<Pin>,
    out_pins: Vec<Pin>,
    netlist: Vec<Net<'a>>
}

impl<'a> Component<'a> {
    pub fn new() -> Component<'a> {
        ...
    }

    pub fn add_subcomponent( & mut self, comp: Component<'a> ) {
        // -> &Box<Component<'a>> ??
        ....
    }
}

在 C++ 中，Net 可以很容易地实现为指向组件的指针数组，但我不确定在 Rust 中执行此操作的最佳方法，我想我应该使用借用的指针？或者有更好的方法吗？

考虑以下主要内容：

fn main() {
    let sub1 = Component::new();
    let sub2 = Component::new();
    let circuit = Component::new();

    circuit.add_subcomponent( sub1 );
    circuit.add_subcomponent( sub2 );
    // sub1 and sub2 are now empty...
}

如何配置电路以在 sub1 和 sub2 之间创建网络？我可以 add_subcomponent returns 借用指向添加组件的指针吗？还是盒子？

如果有人能指出正确的方向，那就太好了。

非常感谢。

Answer 1

你不能在 safe rust 中表示任意图形结构。

实现此模式的最佳方法是使用不安全代码和原始指针，或将此功能包装在安全 api 中的现有抽象，例如 http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

例如，典型的双向链表是：

struct Node {
  next: Option<Node>, // Each node 'owns' the next one
  prev: *mut Node     // Backrefs are unsafe
}

已经有许多 'safe' 实现浮出水面，你有这样的东西：

struct Node {
    id: u32,
    next: u32,
    prev: u32
}
struct Nodes {
  all:Vec<Node>,
  root:Option<Node>
}

这是 'technically' 安全的，但这是一个糟糕的模式；它通过手动实现原始指针来打破所有安全规则。我强烈反对。

您可以尝试使用引用，例如：

struct Container<'a> {
  edges:Vec<Edge<'a>>,
  pub root: Node
}

struct Node {
  children:Vec<Node>  
}

struct Edge<'a> {
  n1: &'a Node,
  n2: &'a Node
}

...但是您几乎会立即跌入借用支票的地狱。例如，当您删除一个节点时，借用检查器如何知道 'edges' 中的关联链接不再有效？

虽然您可以定义结构，但填充它们将非常麻烦。

我知道这可能不是一个令人满意的答案；您可能会发现在 github 中搜索 'rust graph' 和 'rust tree' 并查看其他人已完成的实现很有用。

通常，它们强制将子树的单一所有权授予父对象。

如何建模复杂的递归数据结构（图形）？

How to model complex recursive data structures (graphs)?

rust