6 个版本
0.4.1 | 2024 年 3 月 17 日 |
---|---|
0.4.0 |
|
0.3.2 | 2019 年 4 月 9 日 |
0.3.1 | 2019 年 1 月 24 日 |
0.1.0 | 2017 年 6 月 21 日 |
#240 在 数据结构
3,619 每月下载量
用于 9 个包(4 个直接使用)
165KB
2.5K SLoC
stable-vec
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 License,版本 2.0,(LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
- MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)
。
贡献
除非您明确声明,否则任何根据 Apache-2.0 许可证定义提交给作品并由您有意包含在内的贡献,将根据上述方式双许可,不附加任何额外的条款或条件。