GenValue

GenValue是一个用于在Vec中使用值和带有生成索引的库。

生成索引为Vec提供了一个标识符，它始终可以引用相同的值（除非值被删除），同时有效地重用内存。

生成索引在实体组件系统中常用。

此库是对该想法的简单、直观和通用实现。在大多数系统中，可以根据用例构建一个优化和性能更好的版本。

文档

• 最新API文档

安装

[dependencies]
gen_value = "0.7.0"

示例

使用具有与值和索引相关联的生成的Vec。

use gen_value::{vec::GenVec, Error};

#[derive(Debug, PartialEq)]
struct Value<T>(T);

// * The element type is `Value<u32>`.
// * The generation type by default is a `usize`.
// * The index type by default is a `usize`.
// * The generational index type (index type, generation type)
//   by default is a tuple `(usize, usize)`.
let mut gen_vec = GenVec::<Value<u32>>::default();

// Insert entities
let first_entity_index: (usize, usize) = gen_vec.insert(Value(42))?;
let other_entity_index = gen_vec.insert(Value(9))?;
assert_eq!(gen_vec.get(first_entity_index).ok(), Some(&Value(42)));
assert_eq!(*gen_vec.get(other_entity_index)?, Value(9));
assert_eq!(gen_vec.len(), 2);

// Remove first entity's value
gen_vec.remove(first_entity_index)?;

// Other entity can still be retrieved with same index 
assert_eq!(*gen_vec.get(other_entity_index)?, Value(9));
// Cannot get first entity's value
assert_eq!(gen_vec.get(first_entity_index).ok(), None);
// `Vec` length is still 2
assert_eq!(gen_vec.len(), 2);

// Insert last entity
let last_entity_index = gen_vec.insert(Value(3))?;
assert_eq!(*gen_vec.get(other_entity_index)?, Value(9));
assert_eq!(*gen_vec.get(last_entity_index)?, Value(3));
// First entity index still cannot access a value
assert!(gen_vec.get(first_entity_index).is_err());
assert_eq!(gen_vec.len(), 2);

// The indexes and generations used
assert_eq!(first_entity_index, (0, 0));
assert_eq!(other_entity_index, (1, 0));
// The last entity re-used index 0 but with a newer generation
assert_eq!(last_entity_index, (0, 1));

Ok::<_, Error>(())

动机

访问Vec中的元素相对较快。给定一个索引，从向量的开始进行相对简单的偏移量计算，就可以读取一个元素。更好的是，因为向量的元素在内存中相邻，所以向量非常适合CPU缓存预取。

相比之下，HashMap需要哈希一个键，然后可能需要跟随多个指针来找到元素。BTreeMap可能需要比较几次才能找到具有所需键的条目。两者都应比通过索引在Vec中访问元素相对较慢。

另一方面，Vec索引通常不是元素的稳定标识符。通过插入新元素或删除元素，元素的位通常会发生变化，因此索引可能会随着时间的推移访问不同的元素。

对于HashMap和BTreeMap，键是值的稳定标识符（只要键遵循文档中的不变性）。如果使用键在映射中存储一个值，可以使用相同的键在以后检索该值（假设值没有被删除）。键可以被复制到程序的各个部分，并且以后仍然可以使用。

在许多使用场景中，将稳定的标识符映射到值是有需求的。

我们如何保持稳定的标识符同时试图保持Vec的性能属性呢？

永不移动元素

Vec保持稳定标识符的一种方法是不移动元素。一旦值被推送到Vec的末尾，该值将始终具有相同的索引。所有移动元素的运算都可以被禁止（例如，在指定位置插入新元素）。

然而，从集合中删除元素是重要的功能。一个可能的解决方案是使用一个“已删除”的墓碑值，通过使用Vec>。值被推入为Some(T)，当被删除时将被设置为None。索引成为元素的稳定标识符。

不幸的是，随着元素被设置为None而被删除，未使用的内存越来越多。

带代数的索引和值

代数索引是最大化内存使用率的同时保持元素位置不变的可能解决方案。Vec中的每个元素都与一个代数值相关联，这通常是一个整数。代数索引是一个带有代数值的索引。根据代数值是否匹配或一个代数值是否大于另一个，运算将成功。

Vec变成Vec<(G, T)>，其中G是代数类型。单个元素索引I变成(I, G)。

因此，在一个Vec<(usize, Person)>中，索引为9的元素可能有一个代数值2和一个Person值。如果使用代数索引(9, 2)，则读取第9个偏移量的元素。然后，与Person值关联的代数与与索引关联的代数进行比较。由于两者都是2，因此运算成功。如果代数索引是(9, 1)，那么运算将失败，因为代数不会匹配。

假设存在一个代数索引（(3,1)）和索引为3的Vec具有代数为1的值。当元素被"移除"时，与Vec中的值关联的代数会增加。因此，Vec在索引3处的代数将是2。由于代数不再相等，代数索引（(3,1)）将无法再用于访问索引3处的Vec值。虽然在Rust的术语中，值并非技术上被丢弃，但实际上已从访问中移除。

具有最新代数的索引可用于存储新值，因此重用内存而不是留作未使用。使用先前代数的索引的实体将无法访问已移除的值，而使用最新代数的索引的实体将检索索引处的值。

新索引的分配和代数的增加必须逻辑正确，以确保程序正确性。

类似项目

• generational-arena
• gen-vec

这两个crate都受到Catherine West在2018年RustConf上的优秀闭幕演讲的启发。

与其他crate相比，这个crate的主要区别在于它通过类型参数直接控制索引类型和代数类型。如果一个用例只需要代数为u8，这个crate可以使用一个u8。代数索引类型本身可以指定（而不是使用单个Index类型或(I, G)元组），对于一些类型安全用例。每个crate都选择了不同的API来公开。