Crate stable_vec

A 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 StableVec.

This crate uses #![no_std] but requires the alloc crate.

Why?

The standard 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:

1. It has a linear O(n) time complexity
2. It invalidates all indices of the shifted elements

Invalidating an index means that a given index i who referred to an element 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.

How?

We can trade O(1) deletions and stable indices for a higher memory consumption.

When 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 to understand:

The memory requirement of this data structure is O(|inserted elements|); instead of 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.

Why not?

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 HashMap with 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.

Use of unsafe in this crate

Unfortunately, implementing the features of this crate in a fast manner requires 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 unsafe makes things faster.

This crate takes great care to ensure that all instances of unsafe are 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 unsafe code.

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 unsafe code that is not necessary and you can show that removing it does not decrease execution speed, please also open an issue or PR!

Modules

• core
  Core trait definition and implementations.
• iter
  Contains all iterator types and implementations.

Structs

• StableVecFacade
  A Vec<T>-like collection which guarantees stable indices and features O(1) deletion of elements.

Type Aliases

• ExternStableVec
  A stable vector which stores the “deleted information” externally in a bit vector.
• InlineStableVec
  A stable vector which stores the “deleted information” inline. This is very close to Vec<Option<T>>.
• StableVec
  A stable vector with the default core implementation.