Crate slotmap[−][src]
slotmap
This library provides two containers with persistent unique keys to access
stored values, SlotMap
and 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 BTreeMap
or 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
manner.
Examples
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.
Serialization through serde
Both Key
and the slot maps have full (de)seralization support through
the 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
is safe.
Why not slab
?
Unlike 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 DenseSlotMap
also provides faster iteration than slab
does. Additionally, at the time
of writing slab
does not support serialization.
Choosing SlotMap
or DenseSlotMap
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 SlotMap
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
provide a 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.
Performance characteristics and implementation details
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.
Re-exports
pub use dense::DenseSlotMap; |
Modules
dense |
Contains the dense slot map implementation. |
Structs
Drain |
A draining iterator for |
IntoIter |
An iterator that moves key-value pairs out of a |
Iter |
An iterator over the key-value pairs in a |
IterMut |
A mutable iterator over the key-value pairs in a |
Key |
Key used to access stored values in a slot map. |
Keys |
An iterator over the keys in a |
SlotMap |
Slot map, storage with stable unique keys. |
Values |
An iterator over the values in a |
ValuesMut |
A mutable iterator over the values in a |