#arena #index #options #bitvec #memory-allocator

no-std stable-vec

类似于 Vec 的集合,保证稳定的索引和 O(1) 元素删除功能(在语义上与 Vec<Option<T>> 类似)。在图或类似数据结构中分配很有用。

6 个版本

0.4.1 2024 年 3 月 17 日
0.4.0 2019 年 8 月 27 日
0.3.2 2019 年 4 月 9 日
0.3.1 2019 年 1 月 24 日
0.1.0 2017 年 6 月 21 日

#240数据结构

Download history 665/week @ 2024-04-14 827/week @ 2024-04-21 412/week @ 2024-04-28 464/week @ 2024-05-05 509/week @ 2024-05-12 466/week @ 2024-05-19 468/week @ 2024-05-26 533/week @ 2024-06-02 385/week @ 2024-06-09 596/week @ 2024-06-16 619/week @ 2024-06-23 695/week @ 2024-06-30 735/week @ 2024-07-07 1224/week @ 2024-07-14 868/week @ 2024-07-21 740/week @ 2024-07-28

3,619 每月下载量
用于 9 个包(4 个直接使用)

MIT/Apache

165KB
2.5K SLoC

stable-vec

CI status of master Crates.io Version docs.rs

A Vec<T>-like collection which guarantees stable indices and features O(1) element removal at the cost of wasting some memory. It is semantically very similar to Vec<Option<T>>, but with a more optimized memory layout and a more convenient API. This data structure is very useful as a foundation to implement other data structures like graphs and polygon meshes. In those situations, stable-vec functions a bit like an arena memory allocator. This crate works in #![no_std] context (it needs the alloc crate, though).

This crate implements different strategies to store the information. As these strategies have slightly different performance characteristics, the user can choose which to use. The two main strategies are

  • 类似 Vec<T>BitVec (默认使用),和
  • 类似 Vec<Option<T>>

请参阅 文档 了解更多信息。示例

let mut sv = StableVec::new();
let star_idx = sv.push('');
let heart_idx = sv.push('');
let lamda_idx = sv.push('λ');

// Deleting an element does not invalidate any other indices.
sv.remove(star_idx);
assert_eq!(sv[heart_idx], '');
assert_eq!(sv[lamda_idx], 'λ');

// You can insert into empty slots (again, without invalidating any indices)
sv.insert(star_idx, '');

// We can also reserve memory (create new empty slots) and insert into
// these new slots. All slots up to `sv.capacity()` can be accessed.
sv.reserve_for(15);
assert_eq!(sv.get(15), None);
sv.insert(15, '');

// The final state of the stable vec
assert_eq!(sv.get(0), Some(&''));
assert_eq!(sv.get(1), Some(&''));
assert_eq!(sv.get(2), Some(&'λ'));
assert_eq!(sv.get(3), None);
assert_eq!(sv.get(14), None);
assert_eq!(sv.get(15), Some(&''));

替代方案?关于 slab 怎么样?

类似于 slab 的 crate 与 stable-vec 非常相似,但下载量要大得多。尽管非常相似,但它们之间有一些差异可能对您很重要。

  • slab 会重用已删除条目的键,而 stable-vec 则不会自动进行。
  • slab 在内部进行更多的管理,以便快速知道哪些键可以重用以及在哪里插入。这可能会产生一点开销。最值得注意的是:在 slab 中的底层 Vec 中的每个条目至少为 size_of::<usize>() + 1 字节大。如果您正在存储小元素,这可能会造成显著的内存使用开销。
  • slab 具有固定的内存布局,而 stable-vec 允许您选择不同的布局。这些布局具有不同的性能特征,您可能需要根据您的需求选择合适的布局。
  • stable-vec 的 API 相对更底层。

许可证

根据您的选择,受以下任一许可证的许可:

贡献

除非您明确声明,否则任何根据 Apache-2.0 许可证定义提交给作品并由您有意包含在内的贡献,将根据上述方式双许可,不附加任何额外的条款或条件。

依赖关系