如何建模复杂的递归数据结构(图)? [英] How to model complex recursive data structures (graphs)?

问题描述

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

I am very interested in Rust and am now starting my first non-trivial project in the language. I am still having a bit of trouble fully understanding the concepts of borrowing and lifetime.

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

The application is a logic gate simulator in which components are defined recursively (in terms of other components and their interconnections).

我目前的计划是像在 C++ 中一样实现这一点，通过拥有一个 Component 结构，该结构拥有一个组件向量(它的子组件)和一个描述这些组件之间相互连接的网络向量:

My current plan is to implement this similarly as I would in C++ by having a Component structure owning a vector of Components (its sub-components) and a vector of Nets describing the inter-connections between those components:

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 中执行此操作的最佳方法，我想我应该使用借用的指针吗?或者有更好的方法吗?

In C++, Net would be easy to implement as an array of pointers to Components but I am not sure of the best way to do this in Rust, I suppose I should use borrowed pointers? Or is there a better way?

主要考虑以下几点:

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 返回一个借用的指向添加的组件的指针吗?还是盒子?

How can I configure circuit to create a net between sub1 and sub2? Shall I have add_subcomponent returns a borrowed pointer to the added Component? or the Box?

如果有人能指出我正确的方向就好了.

It would be great if someone could point me in the right direction.

非常感谢.

推荐答案

你不能在 safe Rust 中表示任意图形结构.

You can't represent an arbitrary graph structure in safe rust.

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

The best way to implement this pattern is to use unsafe code and raw pointers, or an existing abstraction that wraps this functionality in a safe api, for example http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

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

For example, the typical bi directional linked list would be:

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

有许多安全"的实现，比如:

There have been a number of 'safe' implementations floating around, where you have something like:

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

这在技术上"是安全的，但这是一个可怕的模式；它通过手动实现原始指针打破了所有安全规则.我强烈建议不要这样做.

This is 'technically' safe, but it's a terrible pattern; it breaks all the safety rules by just manually implementing raw pointers. I strongly advise against it.

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

You could try using references, eg:

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

struct Node {
  children:Vec<Node>  
}

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

...但是您几乎会立即陷入借用检查器的地狱.例如，当您删除一个节点时，借用检查器如何知道边"中的关联链接不再有效?

...but you'll stumble almost immediately into borrow checker hell. For example, when you remove a node, how does the borrow checker know that the associated links in 'edges' are no longer valid?

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

Although you might be able to define the structures, populating them will be extremely troublesome.

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

I know that's probably a quite unsatisfying answer; you may find it useful to search github for 'rust graph' and 'rust tree' and look at the implementations other people have done.

通常，它们将子树的单一所有权强制给父对象.

Typically they enforce single-ownership of a sub-tree to a parent object.

这篇关于如何建模复杂的递归数据结构(图)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！