6个版本
| 0.2.3 | 2023年6月1日 |
|---|---|
| 0.2.2 | 2023年6月1日 |
| 0.2.1 | 2023年5月31日 |
| 0.1.1 | 2023年5月29日 |
#2244 in 数据结构
每月60次下载
265KB
419 行
slicedvec
这是一个Rust crate，它提供了一个类型 SlicedVec<T>，它使用单个 Vec<Vec<T>> 进行存储，以模拟 Vec<Vec<T>> 的某些方面。其主要目的是支持交换-删除习惯用法。当反复创建和销毁许多对象时，可以使用交换-删除习惯用法来消除大多数分配。但是，如果存储的对象本身进行分配，则不适用，例如，当使用 Vec<Vec<Vec<T>>
lib.rs:
提供了两个结构：SlicedVec 和 SlicedSlab。目标用例是需要反复构建和丢弃短、运行时大小的浮点数序列。除非使用池或其他机制，否则使用 Vec<Vec<T>> 可能会导致分配器抖动。《SlicedVec》将运行时大小的切片集合存储在一个向量中。它模拟了一个 Vec<&[T]>，但拥有并管理自己的存储。提供了常数时间、非顺序保持的插入和删除方法。重复生成 push 和 swap_remove（或 swap_truncate） 不会分配，因为存储容量将根据需要增长。
SlicedSlab 是基于 SlicedVec 构建的，并返回分配值序列的稳定键。当一个序列被插入到片块中时，它会返回一个键。可以使用该键从片块中检索或删除序列。删除操作仅将槽标记为未占用，后续的插入将覆盖它而不需要分配。请注意，删除序列的元素将推迟到插入到该位置。如果片块变得过于稀疏，提供了重新键和压缩片块的方法。空槽存储在 BTreeSet 中，因此大多数操作具有与开放槽数量对数复杂度相关的复杂度。在大多数情况下，开放槽集将非常小，并且完全位于缓存中。如果它变得过大，则需要压缩以提高性能。始终插入到可用最低等级槽位中的优势超过了 BTreeSet 的小成本，因为它减少了碎片化。
示例
use rand::{rngs::SmallRng, Rng, SeedableRng};
use slicedvec::SlicedVec;
let mut rng = SmallRng::from_entropy();
let mut x1 = SlicedVec::with_capacity(1000, 20);
x1.push_vec(
std::iter::repeat_with(|| rng.gen())
.take(20 * 1000)
.collect::<Vec<_>>(),
);
let x1_insert: Vec<Vec<usize>> =
std::iter::repeat_with(|| std::iter::repeat_with(|| rng.gen()).take(20).collect())
.take(500)
.collect();
for i in 0..500 { x1.swap_truncate(i) }
for i in 0..500 { x1.push(&x1_insert[i]) }