A sparse mapping of entity references.
A SparseMap<K, V>
map provides:
- Memory usage equivalent to
SecondaryMap<K, u32>
+ Vec<V>
, so much smaller than
SecondaryMap<K, V>
for sparse mappings of larger V
types.
- Constant time lookup, slightly slower than
SecondaryMap
.
- A very fast, constant time
clear()
operation.
- Fast insert and erase operations.
- Stable iteration that is as fast as a
Vec<V>
.
When should we use a SparseMap
instead of a secondary SecondaryMap
? First of all,
SparseMap
does not provide the functionality of a PrimaryMap
which can allocate and assign
entity references to objects as they are pushed onto the map. It is only the secondary entity
maps that can be replaced with a SparseMap
.
- A secondary entity map assigns a default mapping to all keys. It doesn't distinguish between
an unmapped key and one that maps to the default value.
SparseMap
does not require
Default
values, and it tracks accurately if a key has been mapped or not.
- Iterating over the contents of an
SecondaryMap
is linear in the size of the key space,
while iterating over a SparseMap
is linear in the number of elements in the mapping. This
is an advantage precisely when the mapping is sparse.
SparseMap::clear()
is constant time and super-fast. SecondaryMap::clear()
is linear in
the size of the key space. (Or, rather the required resize()
call following the clear()
is).
SparseMap
requires the values to implement SparseMapValue<K>
which means that they must
contain their own key.
Create a new empty mapping.
Returns the number of elements in the map.
Returns true is the map contains no elements.
Remove all elements from the mapping.
Returns a reference to the value corresponding to the key.
Returns a mutable reference to the value corresponding to the key.
Note that the returned value must not be mutated in a way that would change its key. This
would invalidate the sparse set data structure.
Return true
if the map contains a value corresponding to key
.
Insert a value into the map.
If the map did not have this key present, None
is returned.
If the map did have this key present, the value is updated, and the old value is returned.
It is not necessary to provide a key since the value knows its own key already.
Remove a value from the map and return it.
Remove the last value from the map.
Get an iterator over the values in the map.
The iteration order is entirely determined by the preceding sequence of insert
and
remove
operations. In particular, if no elements were removed, this is the insertion
order.
Get the values as a slice.
Iterating over the elements of a set.
The type of the elements being iterated over.
Which kind of iterator are we turning this into?
🔬 This is a nightly-only experimental API. (try_from
)
The type returned in the event of a conversion error.
🔬 This is a nightly-only experimental API. (try_from
)
🔬 This is a nightly-only experimental API. (try_from
)
The type returned in the event of a conversion error.
🔬 This is a nightly-only experimental API. (try_from
)
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more
🔬 This is a nightly-only experimental API. (get_type_id
)
this method will likely be replaced by an associated static