Vec<T>-like collection which guarantees stable indices and features
O(1) deletion of elements.
You can find nearly all the relevant documentation on the type
StableVecFacade. This is the main type which is configurable over the
core implementation. To use a pre-configured stable vector, use
This crate uses
#![no_std] but requires the
Vec<T> always stores all elements contiguously. While this
has many advantages (most notable: cache friendliness), it has the
disadvantage that you can't simply remove an element from the middle; at
least not without shifting all elements after it to the left. And this has
two major drawbacks:
- It has a linear O(n) time complexity
- It invalidates all indices of the shifted elements
Invalidating an index means that a given index
i who referred to an
a before, now refers to another element
b. On the contrary, a
stable index means, that the index always refers to the same element.
Stable indices are needed in quite a few situations. One example are graph data structures (or complex data structures in general). Instead of allocating heap memory for every node and edge, all nodes and all edges are stored in a vector (each). But how does the programmer unambiguously refer to one specific node? A pointer is not possible due to the reallocation strategy of most dynamically growing arrays (the pointer itself is not stable). Thus, often the index is used.
But in order to use the index, it has to be stable. This is one example, where this data structure comes into play.
We can trade O(1) deletions and stable indices for a higher memory consumption.
StableVec::remove() is called, the element is just marked as
"deleted" (and the actual element is dropped), but other than that, nothing
happens. This has the very obvious disadvantage that deleted objects (so
called empty slots) just waste space. This is also the most important thing
The memory requirement of this data structure is
O(|inserted elements| - |removed elements|). The latter is the
memory requirement of normal
Vec<T>. Thus, if deletions are far more
numerous than insertions in your situation, then this data structure is
probably not fitting your needs.
As mentioned above, this data structure is rather simple and has many disadvantages on its own. Here are some reason not to use it:
- You don't need stable indices or O(1) removal
- Your deletions significantly outnumber your insertions
- You want to choose your keys/indices
- Lookup times do not matter so much to you
Especially in the last two cases, you could consider using a
integer keys, best paired with a fast hash function for small keys.
If you not only want stable indices, but stable pointers, you might want to use something similar to a linked list. Although: think carefully about your problem before using a linked list.
Unfortunately, implementing the features of this crate in a fast manner
unsafe. This was measured in micro-benchmarks (included in this
repository) and on a larger project using this crate. Thus, the use of
unsafe is measurement-guided and not just because it was assumed
makes things faster.
This crate takes great care to ensure that all instances of
actually safe. All methods on the (low level)
Core trait have extensive
documentation of preconditions, invariants and postconditions. Comments in
functions usually describe why
unsafe is safe. This crate contains a
fairly large number of unit tests and some tests with randomized input.
These tests are executed with
miri to try to catch UB caused by invalid
That said, of course it cannot be guaranteed this crate is perfectly safe.
If you think you found an instance of incorrect usage of
unsafe or any
UB, don't hesitate to open an issue immediately. Also, if you find
code that is not necessary and you can show that removing it does not
decrease execution speed, please also open an issue or PR!
Contains all iterator types and implementations.
A stable vector which stores the "deleted information" externally in a bit vector.
A stable vector which stores the "deleted information" inline. This is very
A stable vector with the default core implementation.