IdVec

将元素插入此 Vec 将返回对该新元素的持久、类型安全的索引。

用法

let mut words = IdVec::new();

let id_hello: Id<&str> = words.insert("hello");
let id_world = words.insert("world");

println!("{:?} -> {:?}", id_hello, words.get(id_hello));

更多示例，请参阅 lib.rs。

您可以将 IdVec 视为一个重用槽位的向量。它将新元素插入到旧元素被移除的地方，而不是将所有剩余元素移动一个位置。这允许使用索引来引用元素，即使从向量中删除其他元素，这些索引仍然有效。

这个特定库的目标是在资源使用和 API 复杂性方面都非常最小化。因此，它没有运行时系统来检测已删除 Id 的错误使用。用户必须注意不要使用已删除的 Id。

包含此库

要将此包添加到您的项目，只需将以下行添加到您的 Cargo.toml 依赖项中

[dependencies]
id-vec = "*"

动机

在 Rust 中，图可能相当难以构建，因为简单的 &'a T 会阻止对图的任何修改。使用 Ref<Cell<T>> 被认为是非惯用的，因为它绕过了 Rust 的安全机制。

解决此问题的一种方法是通过使用索引，并将图的所有节点存储在一个向量中。每个节点将存储其连接节点的索引，而不是直接引用它们。然而，这要求所有对节点的操作都必须访问该向量，这可能感觉非常不直观。尽管如此，我认为这种方法是最符合惯用性和安全的。

该库通过引入 ID（本质上是无类型安全的索引）来简化基于索引的方法。通过只允许使用 Id<T>（而不是任何无符号数字）作为向量的索引来实现安全性。

该库提供了一种专为连接图节点这种用途构建的容器，而不使用任何不安全 Rust。

为什么不使用 Slab？

• 这个库是不同的实现，因此对于某些特殊用例可能具有更好的运行时性能。
• 索引是通过类型安全的 Id<T> 来完成的，而不是使用普通的、安全性较低的 usize。此外，使用 usize 错误地暗示了一种线性排序，就像在常规的 Vec 中一样。
• DoubleEndedIterator，启用 .iter().rev()
• map.pack(...)，该功能会重新排列映射，以删除所有未使用的槽位，在一系列删除操作后减少内存开销。

架构

本项目包含两个核心结构：映射本身和 ID。ID 只是一个包装索引的新类型，但它有一个类型参数来提高索引的类型安全性。映射在内部是一个向量，但它重新使用已删除的槽位。它是通过将已删除元素的索引存储在哈希集中来实现的，这在大部分已填充的映射中内存效率高，在插入新元素时速度快，但可能不如 BitVec 在索引时快。

其他有趣的crate

• Slab:

  具有相同的目的，但实现和功能集不同。

• Froggy：组件-图-系统

  它也包含一个类似的数据结构，利用 Ids，但使用 Rc<T> 和 Weak<T> 进行更多运行时检查，这是我希望避免的。