generational-arena

一个安全的竞技场分配器，通过使用代索引支持删除，而不会遭受ABA问题。

受到Catherine West在2018年RustConf上的闭幕演讲的启发，在那里这些想法（以及许多其他想法！）在游戏编程的实体-组件-系统背景下提出。

什么？为什么？

想象一下你正在处理一个图，并且你想要一次添加和删除单个节点，或者你正在编写一个游戏，其世界由许多相互引用的对象组成，这些对象的生存期取决于用户输入。在这些情况下，匹配Rust的所有权和生存期规则可能会变得复杂。

对于结构体，使用共享所有权（即 Rc<RefCell<T>> 或 Arc<Mutex<T>>）或借用引用（例如 &'a T 或 &'a mut T）是没有意义的。循环规则排除了引用计数类型，而所需的共享可变性规则排除了借用。此外，生存期是动态的，并且不遵循借用数据比借用人持久的纪律。

在这些情况下，可能会让人想将对象存储在Vec<T>中，并通过它们的索引相互引用。这样就没有借用检查或所有权问题！通常，这种解决方案已经足够好了。

然而，现在我们无法从那个Vec<T>中删除单个项，因为当我们不再需要它们时，我们会陷入以下两种情况之一：

• 打乱删除项之后每个元素的索引，或者

• 遭受ABA问题。进一步解释，如果我们尝试用Vec<Option<T>>替换Vec<T>，并通过将其设置为None来删除一个元素，那么就会产生这种有问题的序列

  • obj1在索引i处引用obj2

  • 有人从索引i处删除了obj2，将该元素设置为None

  • 第三件事分配了obj3，它最终位于索引i处，因为该索引处的元素是None，因此可用于分配

  • obj1尝试在索引i处获取obj2，但错误地得到了obj3，而实际上获取应该失败。

通过向集合引入单调递增的生成器计数器，将每个元素与其插入时的生成器关联起来，并通过索引和元素插入时的生成器对从集合中获取元素，然后我们可以解决上述ABA问题。当索引集合时，如果索引对的生成器与该索引处的元素的生成器不匹配，则该操作失败。

功能

• 零unsafe
• 经过良好测试，包括快速检查
• no_std兼容性
• 您期望的所有特质实现：IntoIterator，FromIterator，Extend等...

用法

首先，将generational-arena添加到您的Cargo.toml中

[dependencies]
generational-arena = "0.2"

然后，导入该crate并使用generational_arena::Arena类型！

extern crate generational_arena;
use generational_arena::Arena;

let mut arena = Arena::new();

// Insert some elements into the arena.
let rza = arena.insert("Robert Fitzgerald Diggs");
let gza = arena.insert("Gary Grice");
let bill = arena.insert("Bill Gates");

// Inserted elements can be accessed infallibly via indexing (and missing
// entries will panic).
assert_eq!(arena[rza], "Robert Fitzgerald Diggs");

// Alternatively, the `get` and `get_mut` methods provide fallible lookup.
if let Some(genius) = arena.get(gza) {
    println!("The gza gza genius: {}", genius);
}
if let Some(val) = arena.get_mut(bill) {
    *val = "Bill Gates doesn't belong in this set...";
}

// We can remove elements.
arena.remove(bill);

// Insert a new one.
let murray = arena.insert("Bill Murray");

// The arena does not contain `bill` anymore, but it does contain `murray`, even
// though they are almost certainly at the same index within the arena in
// practice. Ambiguities are resolved with an associated generation tag.
assert!(!arena.contains(bill));
assert!(arena.contains(murray));

// Iterate over everything inside the arena.
for (idx, value) in &arena {
    println!("{:?} is at {:?}", value, idx);
}

no_std

为了启用no_std兼容性，请禁用默认启用的“std”功能。

[dependencies]
generational-arena = { version = "0.2", default-features = false }

使用serde进行序列化和反序列化

为了启用序列化/反序列化支持，请启用“serde”功能。

[dependencies]
generational-arena = { version = "0.2", features = ["serde"] }