Struct SparseSet 

pub struct SparseSet<I, V: 'static> { /* private fields */ }

A map from I to V that combines dense and sparse storage.

This is implemented as a sparse array mapping keys to dense indexes, plus dense arrays of indexes and keys.

The key type, I, must implement SparseSetIndex to allow conversion to and from array indexes.

This supports fast O(1) lookups, since they consist of one array index to map the key to a dense index, followed by a second array index to find the value.

This may use a lot of excess memory if the set is sparsely populated, since it stores an empty entry for each key.

Compared to a simple Vec<Option<V>>, the dense storage of values takes less memory when V is large, although the overhead of tracking which entries have values may make it larger when V is small or the set is densely populated.

Implementations

impl<I: SparseSetIndex, V> SparseSet<I, V>

pub fn len(&self) -> usize

Returns the number of elements in the sparse set.

pub fn contains(&self, index: I) -> bool

Returns true if the sparse set contains a value for index.

pub fn get(&self, index: I) -> Option<&V>

Returns a reference to the value for index.

Returns None if index does not have a value in the sparse set.

pub fn get_mut(&mut self, index: I) -> Option<&mut V>

Returns a mutable reference to the value for index.

Returns None if index does not have a value in the sparse set.

pub fn indices(&self) -> &[I]

Returns an iterator visiting all keys (indices) in arbitrary order.

pub fn values(&self) -> impl Iterator<Item = &V>

Returns an iterator visiting all values in arbitrary order.

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V>

Returns an iterator visiting all values mutably in arbitrary order.

pub fn iter(&self) -> impl Iterator<Item = (&I, &V)>

Returns an iterator visiting all key-value pairs in arbitrary order, with references to the values.

pub fn iter_mut(&mut self) -> impl Iterator<Item = (&I, &mut V)>

Returns an iterator visiting all key-value pairs in arbitrary order, with mutable references to the values.

impl<I, V> SparseSet<I, V>

pub const fn new() -> Self

Creates a new SparseSet.

impl<I: SparseSetIndex, V> SparseSet<I, V>

pub fn with_capacity(capacity: usize) -> Self

Creates a new SparseSet with a specified initial capacity.

Panics

• Panics if the new capacity of the allocation overflows isize::MAX bytes.
• Panics if the new allocation causes an out-of-memory error.

pub fn capacity(&self) -> usize

Returns the total number of elements the SparseSet can hold without needing to reallocate.

pub fn insert(&mut self, index: I, value: V)

Inserts value at index.

If a value was already present at index, it will be overwritten.

Panics

• Panics if the insertion forces an reallocation and the new capacity overflows isize::MAX bytes.
• Panics if the insertion forces an reallocation and causes an out-of-memory error.

pub fn get_or_insert_with( &mut self, index: I, func: impl FnOnce() -> V, ) -> &mut V

Returns a reference to the value for index, inserting one computed from func if not already present.

Panics

• Panics if the insertion forces an reallocation and the new capacity overflows isize::MAX bytes.
• Panics if the insertion forces an reallocation and causes an out-of-memory error.

pub fn is_empty(&self) -> bool

Returns true if the sparse set contains no elements.

pub fn remove(&mut self, index: I) -> Option<V>

Removes and returns the value for index.

Returns None if index does not have a value in the sparse set.

pub fn clear(&mut self)

Clears all of the elements from the sparse set.

Panics

• Panics if any of the keys or values implements Drop and any of those panic.

Trait Implementations

impl<I: Debug, V: Debug + 'static> Debug for SparseSet<I, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<I: SparseSetIndex, V> Default for SparseSet<I, V>

fn default() -> Self

Returns the “default value” for a type.