rust - 如何使用 HashMap 创建一个结构，其中的键与容器的类型相同

Question

我正在浏览 Mazes for Programmers并认为我会尝试用 Rust 来做(原始代码在 Ruby 中)。

您在本书中要做的第一件事就是实现 Cell包含指向其他单元格的链接的类。天真地，我以为我可以做这样的事情:

pub struct Cell {
    row: u32,
    column: u32,

    links: HashMap<Box<Cell>, bool>,
}

想法是每个 Cell在迷宫中知道它连接到哪些其他单元格，并且 Maze只是 Cells 的集合.不幸的是，这导致了 Rust 的借用和所有权语义的双向链表问题，我不确定如何解决这个问题。

具体来说，我不知道如何实现 link这里:

impl Cell {
    pub fn new (row: u32, column: u32) -> Cell {
        return Cell {
            row: row,
            column: column,
            links: HashMap::new(),
        };
    }

    pub fn link(&mut self, other: &mut Cell, bidi: bool) {
        self.links.insert(Box::new(other), true); // cannot get anything even remotely like this to work here.
    }
}

我查看了 Rust Book 关于选择保证的部分，其中有一些关于指针包装器和抽象的各自选择的好信息，但我真的不确定如何推理我想要的东西与编译器一起做。

我想我想要每个 Cell结构维护(通过嵌入式 HashMap )对其他 Cells 的引用(在该术语的非显式使用中)它已连接到，但由于该链接将是双向的，在我看来我最终将使用 Rc或类似的东西。

也有可能我应该远离书中 Ruby 代码的直译，并考虑一种更地道的方法——可能会忽略 Cell 的问题。结构完全支持更直接的东西，比如大 HashMap的元组。

Answer 1

How can I create a struct with a HashMap where the keys the same type as the container

the original code is in Ruby

我不太熟悉 Ruby，但我知道很多类似的语言，所以我会做一些有根据的猜测。

Ruby 是一个 thoroughly garbage collected language .这意味着您永远无法将某种类型的键存储在 Ruby HashMap 中。您可能认为您正在存储 Cell 类型的 key ，但真正发生的是您将垃圾收集的 指针 存储到 Cell 的一个实例。 .

指针只是某个内存区域的索引。

现在，Rust 是一种不同的语言。在 Rust 中，您可以存储实际的 Cell就在 HashMap 的底层键数组中。换句话说，Rust 给了你更多的控制权，这通常会转化为更好的内存使用和速度。

但随着控制而来的是责任(除非你想破坏事物并快速破坏它们)。在 Rust 中，您应该明确指定谁拥有实例。当您创建一个指向自身的结构(循环图)时，所有权就会变得困惑。

因此实现循环结构的一种方法是移动所有权 concern不等式!

在 Ruby 中，垃圾收集器解决了这个问题。内存管理是垃圾收集器的关注点，您无需处理它即可实现循环结构。

在 Rust 中，你可以通过使用(实验性的)垃圾收集器来做同样的事情，可能是 rust-gc .

或者您可以动手实际管理内存。

这并不像听起来那么难。您所需要的只是一些拥有 Cell 的非循环结构。 Vec<Cell>就足够了。存储 Cell 后在向量中，您不必再担心所有权。因为Cell现在由该矢量拥有，简单明了。您可以制作循环结构，引用 Cell通过它的向量索引，就像 Ruby 使用它的指针一样!

对此有各种各样的变化。当您管理所有权时，您就是老板，选择权在您。您可以使用 memory pools 优化一些算法，也称为竞技场。您可以使用引用计数(那时不需要向量，但您希望在从结构中删除单元格时仔细清除引用 - 以打破引用计数周期)。您可以使用一种双端队列来分块分配内存，但无需像 vector 那样进行重新分配，然后将直接指针存储到该双端队列中。 this reddit discussion 中提到了一些选项.

但原理很简单。确保某些内容( Vec 、 Rc 、 Gc )涵盖了所有权问题。当涵盖这些内容时，您可以像在 Ruby 中一样编程，因为所有权不再是问题。