string - Rust rustc::middle::graph::Graph 与字符串节点索引

Question

我是 rust 的新手(使用 0.10)并通过实现类似于 rustc::middle::graph::Graph 的东西来探索它的使用结构，但使用字符串作为节点索引并将节点存储在 HashMap 中。

假设非静态键，什么是合理有效的字符串所有权策略？ HashMap 是否需要拥有它的键？每个 NodeIndex 都需要拥有它的 str 吗？节点是否可能拥有定义其索引的字符串并让其他所有对象借用该字符串？更一般地说，应该如何在多个数据结构之间共享一个不可变(但非静态)的字符串？如果答案是“视情况而定”，相关的问题是什么？

如果可以在一个地方拥有字符串的所有权并在别处借用它，这是如何实现的？例如，如果 Node 结构被修改为将节点索引存储为字符串，那么 HashMap 和 NodeIndex 将如何使用借用的版本是吗？

Answer 1

Is it possible for the node to own the string that defines its index and have everything else borrow that string?

[...]

If it is possible to have ownership of the string in one place and borrow it elsewhere, how is that accomplished? For example, if the Node struct were modified to store the node index as a string, how would the HashMap and NodeIndex use a borrowed version of it?

并非如此:(对于编译器)不可能验证自引用不会失效，即许多内部借用情况(特别包括这种情况)最终允许类似于

的代码

struct Foo<'a> {
    things: Vec<~str>,
    borrows: Vec<&'a str>
}
let mut foo = Foo { ... };
foo.things.push(~"x");
foo.things.push(~"y");
// foo.things is [~"x", ~"y"]

// try to borrow the ~"y" to put a "y" into borrows
foo.borrows.push(foo.things.get(1).as_slice());

// ... time/SLoC passes ...

// we make the borrowed slice point to freed memory
// by popping/deallocating the ~"y"
foo.things.pop();

编译器很难判断任意修改不会像.pop调用并使内部指针无效。基本上，将对象拥有的数据的自引用放入对象本身必须卡住该对象，因此不会发生进一步的修改(包括移出结构，例如返回它)。

Tl;dr:你不能拥有 Graph 的一部分存储 ~str s 和另一部分存储 &str切成那些 ~str

就是说，如果您要使用一些 unsafe代码，并且只允许 Graph要扩展，即从不删除节点(即从不让 ~str 被释放，直到整个图被销毁)，那么这个的某些版本实际上可以工作。

More generally, how should one share an immutable (but non-static) string amongst several data structures?

您可以使用 Rc<~str> ，每个数据结构都存储自己的指针。有点像

struct Graph<T> {
    nodes: HashMap<Rc<~str>, Node<T>>
}
struct Node<T> {
    name: Rc<~str>,
    data: T,
    outgoing_edges: Vec<Rc<~str>>
}

---

另一种方法是使用双向映射将字符串与简单类型的“内部”索引连接起来，例如

struct Graph<T> {
    index: BiMap<~str, Index>,
    nodes: HashMap<Index, Node<T>>
}
#[deriving(Hash, Eq, TotalEq)]
struct Index { x: uint }

struct Node<T> {
    name: Index,
    data: T,
    outgoing_edges: Vec<Index>    
}

(不幸的是，这是假设的:Rust 的标准库没有这样的 BiMap 类型(还......)。)