|0.4.0||Aug 27, 2019|
|0.3.2||Apr 9, 2019|
|0.3.1||Jan 24, 2019|
|0.1.0||Jun 21, 2017|
#499 in Data structures
622 downloads per month
Used in 5 crates (3 directly)
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:
- something similar to
BitVec(used by default), and
- something similar to
Please refer to the documentation for more information. Example:
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 works very similar to
stable-vec, but has way more downloads.
Despite being very similar, there are a few differences which might be important for you:
slabreuses keys of deleted entries, while
stable-vecdoes not automatically.
slabdoes a bit more management internally to quickly know which keys to reuse and where to insert. This might incur a tiny bit of overhead. Most notably: each entry in the underlying
slabis at least
size_of::<usize>() + 1bytes large. If you're storing small elements, this might be a significant memory usage overhead.
slabhas a fixed memory layout while
stable-veclets you choose between different layouts. These have different performance characteristics and you might want to choose the right one for your situation.
- The API of
stable-vecis a bit more low level.
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.