This library provides two containers with persistent unique keys to access
DenseSlotMap. Upon insertion a key
is returned that can be used to later access or remove the values.
Insertion, deletion and access all take O(1) time with low overhead. Great
for storing collections of objects that need stable, safe references but
have no clear ownership otherwise, such as game entities or graph nodes.
The difference between a
HashMap and a slot map is
that the slot map generates and returns the key when inserting a value. A
key is always unique and will only refer to the value that was inserted.
A slot map's main purpose is to simply own things in a safe and efficient
let mut sm = SlotMap::new(); let foo = sm.insert("foo"); // Key generated on insert. let bar = sm.insert("bar"); assert_eq!(sm[foo], "foo"); assert_eq!(sm[bar], "bar"); sm.remove(bar); let reused = sm.insert("reuse"); // Space from bar reused. assert_eq!(sm.contains_key(bar), false); // After deletion a key stays invalid.
Key and the slot maps have full (de)seralization support through
serde library. A key remains valid for a slot map even after one or
both have been serialized and deserialized! This makes storing or
transferring complicated referential structures and graphs a breeze. Care has
been taken such that deserializing keys and slot maps from untrusted sources
slab, the keys returned by the slots maps are versioned. This
means that once a key is removed, it stays removed, even if the physical
storage inside the slotmap is re-used for new elements. A
also provides faster iteration than
slab does. Additionally, at the time
slab does not support serialization.
The overhead on access with a
Key in a
SlotMap compared to
storing your elements in a
Vec is a mere equality check. However, as
there can be 'holes' in the underlying representation of a
iteration can be inefficient when many slots are unoccupied (a slot gets
unoccupied when an element is removed, and gets filled back up on
insertion). If you often require fast iteration over all values, we also
DenseSlotMap. It trades random access performance for fast
iteration over values by storing the actual values contiguously and using an
extra array access to translate a key into a value index.
Insertion, access and deletion is all O(1) with low overhead by storing the
elements inside a
Vec. Unlike references or indices into a vector,
unless you remove a key it is never invalidated. Behind the scenes each
slot in the vector is a
(value, version) tuple. After insertion the
returned key also contains a version. Only when the stored version and
version in a key match is a key valid. This allows us to reuse space in the
vector after deletion without letting removed keys point to spurious new
elements. After 231 deletions and insertions to the same
underlying slot the version wraps around and such a spurious reference
could potentially occur. It is incredibly unlikely however, and in all
circumstances is the behavior safe. A slot map can hold up to
232 - 1 elements at a time.
A slot map never shrinks - it couldn't even if it wanted to. It needs to
remember for each slot what the latest version is as to not generate
duplicate keys. The overhead for each element in
SlotMap is 8 bytes. In
DenseSlotMap it is 12 bytes.
Contains the dense slot map implementation.
A draining iterator for
An iterator that moves key-value pairs out of a
An iterator over the key-value pairs in a
A mutable iterator over the key-value pairs in a
Key used to access stored values in a slot map.
An iterator over the keys in a
Slot map, storage with stable unique keys.
An iterator over the values in a
A mutable iterator over the values in a
A trait for items that can go in a