Crate slotmap[−][src]
Expand description
slotmap
This library provides a container with persistent unique keys to access
stored values, SlotMap. Upon insertion a key is returned that can be
used to later access or remove the values. Insertion, removal 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.
You can also create (multiple) secondary maps that can map the keys returned
by SlotMap to other values, to associate arbitrary data with objects
stored in slot maps, without hashing required - it’s direct indexing under
the hood.
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 reuse = sm.insert("reuse"); // Space from bar reused. assert_eq!(sm.contains_key(bar), false); // After deletion a key stays invalid. let mut sec = SecondaryMap::new(); sec.insert(foo, "noun"); // We provide the key for secondary maps. sec.insert(reuse, "verb"); for (key, val) in sm { println!("{} is a {}", val, sec[key]); }
Serialization through serde
Both keys 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. If you wish to use these features you must enable the serde
feature flag for slotmap in your Cargo.toml.
slotmap = { version = "...", features = ["serde"] }
Why not slab?
Unlike slab, the keys returned by SlotMap are versioned. This means
that once a key is removed, it stays removed, even if the physical storage
inside the slotmap is reused for new elements. The key is a
permanently unique* reference to the inserted value. Despite
supporting versioning, a SlotMap is not slower than slab, by
internally using carefully checked unsafe code. A HopSlotMap
also provides faster iteration than slab does. Additionally, at the time
of writing slab does not support serialization.
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 - 2 elements at a time.
The memory usage for each slot in SlotMap is 4 + max(sizeof(T), 4)
rounded up to the alignment of T. Similarly it is 4 + max(sizeof(T), 12)
for HopSlotMap.
Choosing SlotMap or HopSlotMap
A SlotMap can never shrink the size of its underlying storage, because
for each storage slot it must remember what the latest stored version was,
even if the slot is empty now. This means that iteration can be slow as it
must iterate over potentially a lot of empty slots.
HopSlotMap solves this by maintaining more information on
insertion/removal, allowing it to iterate only over filled slots by ‘hopping
over’ contiguous blocks of vacant slots. This can give it significantly
better iteration speed. If you expect to iterate over all elements in a
SlotMap a lot, choose HopSlotMap. The downside is that insertion and
removal is roughly twice as slow. Random access is the same speed for both.
Choosing SecondaryMap or SparseSecondaryMap
You want to associate extra data with objects stored in a slot map, so you use (multiple) secondary maps to map keys to that data.
A SecondaryMap is simply a Vec of slots like slot map is, and
essentially provides all the same guarantees as SlotMap does for its
operations (with the exception that you provide the keys as produced by the
primary slot map). This does mean that even if you associate data to only
a single element from the primary slot map, you could need and have to
initialize as much memory as the original.
A SparseSecondaryMap is like a HashMap from keys to objects, however
it automatically removes outdated keys for slots that had their space
reused. You should use this variant if you expect to store some associated
data for only a small portion of the primary slot map.
Custom key types
If you have multiple slot maps it’s an error to use the key of one slot map on another slot map. The result is safe, but unspecified, and can not be detected at runtime, so it can lead to a hard to find bug.
To prevent this, slot maps allow you to specify what the type is of the key
they return, as long as that type implements the Key trait. To aid with
this, the new_key_type! macro is provided that builds such a type for
you. The resulting type is exactly like DefaultKey. So instead of simply
using SlotMap<DefaultKey, Player> you would use:
new_key_type! { struct PlayerKey; } let sm: SlotMap<PlayerKey, Player> = SlotMap::with_key();
Re-exports
pub use hop::HopSlotMap;pub use secondary::SecondaryMap;pub use sparse_secondary::SparseSecondaryMap;Modules
Contains the faster iteration, slower insertion/removal slot map implementation.
Contains the secondary map implementation.
Contains the sparse secondary map implementation.
Macros
A helper macro to conveniently create new key types. If you use a new key type for each slot map you create you can entirely prevent using the wrong key on the wrong slot map.
Structs
The default slot map key type.
A draining iterator for SlotMap.
An iterator that moves key-value pairs out of a SlotMap.
An iterator over the key-value pairs in a SlotMap.
A mutable iterator over the key-value pairs in a SlotMap.
The actual data stored in a Key.
An iterator over the keys in a SlotMap.
Slot map, storage with stable unique keys.
An iterator over the values in a SlotMap.
A mutable iterator over the values in a SlotMap.
Traits
Key used to access stored values in a slot map.