pub struct SparseMap<K, V>where
    K: EntityRef,
    V: SparseMapValue<K>,{ /* private fields */ }
Expand description

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

Compared to SecondaryMap

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.

Implementations§

source§

impl<K, V> SparseMap<K, V>where K: EntityRef, V: SparseMapValue<K>,

source

pub fn new() -> Self

Create a new empty mapping.

source

pub fn len(&self) -> usize

Returns the number of elements in the map.

source

pub fn is_empty(&self) -> bool

Returns true is the map contains no elements.

source

pub fn clear(&mut self)

Remove all elements from the mapping.

source

pub fn get(&self, key: K) -> Option<&V>

Returns a reference to the value corresponding to the key.

source

pub fn get_mut(&mut self, key: K) -> Option<&mut V>

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.

source

pub fn contains_key(&self, key: K) -> bool

Return true if the map contains a value corresponding to key.

source

pub fn insert(&mut self, value: V) -> Option<V>

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.

source

pub fn remove(&mut self, key: K) -> Option<V>

Remove a value from the map and return it.

source

pub fn pop(&mut self) -> Option<V>

Remove the last value from the map.

source

pub fn values(&self) -> Iter<'_, V>

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.

source

pub fn as_slice(&self) -> &[V]

Get the values as a slice.

Trait Implementations§

source§

impl<'a, K, V> IntoIterator for &'a SparseMap<K, V>where K: EntityRef, V: SparseMapValue<K>,

Iterating over the elements of a set.

§

type Item = &'a V

The type of the elements being iterated over.
§

type IntoIter = Iter<'a, V>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Auto Trait Implementations§

§

impl<K, V> RefUnwindSafe for SparseMap<K, V>where K: RefUnwindSafe, V: RefUnwindSafe,

§

impl<K, V> Send for SparseMap<K, V>where K: Send, V: Send,

§

impl<K, V> Sync for SparseMap<K, V>where K: Sync, V: Sync,

§

impl<K, V> Unpin for SparseMap<K, V>where K: Unpin, V: Unpin,

§

impl<K, V> UnwindSafe for SparseMap<K, V>where K: UnwindSafe, V: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.