genmap

一个用于生成映射、处理映射、 whatever you want to call it 的 Rust 包。无论是什么，这是一个随机访问数据结构，它存储一个无序的项目集合，并为每个插入的特定项目提供一个处理。通过处理查找是 O(1) -- 后备存储只是一个 Vec -- 并且项目也可以被移除，这也是 O(1)。处理是小的（两个 usize's）并且易于复制，类似于一个切片。技巧是每个项目都存储一个代际号，这样指向已被移除项目的“悬挂”处理就是无效的。与数组索引不同，如果你从数组中移除一个项目并且一个新项目被放入其位置，旧的处理不会指向新的项目，并且尝试使用它将在运行时失败。

这适用于各种事情：管理大量具有共享所有权的统一事物（如视频游戏资源）、字符串内联，等等。基本上，通过使用项目处理，你可以获得运行时检查的内存安全性：你可以使用处理从映射中获取项目，因为它基本上就是一个数组索引。

实际上这与 Rc 有关，只是 Rc 在克隆 Rc 时进行内存会计，而这是通过查找对象的处理来“解引用”的。引用计数、线程垃圾回收和这种映射都是通过不同的权衡来实现相同的事情（在运行时检查内存安全性）的不同方法。使用引用计数，你不必显式释放项目，并且不能有旧的处理，但是循环需要特殊处理，并且在克隆处理时要支付会计成本。使用这种方法，你必须显式释放项目，但是可以安全地检测旧的处理，会计发生在查找项目时。你也可以将其用作类似 slab 分配器的东西，其中你预先分配大量存储，然后一次性释放。

限制

• 它永远不会释放内存，直到 GenMap 被丢弃（尽管它确实重用空槽）。
• 溢出代际是一个错误。它应该是 u64 而不是 usize 吗？

其他类似的事情

• generational-arena -- 我没找到这个，因此写了 genmap
• 代替。你可能应该直接使用 generational-arena。
• slotmap -- 要求你的项必须是 Copy，这在我看来太过限制。它的 DenseSlotMap 可以解决这个问题，但到那时，有很多选项和权衡需要考虑。我只是想要一样能工作的事情。
• handy -- 很不错，但我不喜欢它所做的某些设计决策：[https://github.com/thomcc/handy/pull/1](https://github.com/thomcc/handy/pull/1)
• slab -- 在我看来并不是一个代际映射，因为它不跟踪代际。
• specs -- 在 specs 中的存储基本上是一种代际映射。但 specs 还增加了许多其他功能。

许可证

MIT/Apache-2.0