pub struct SparseSet<T> { /* private fields */ }Expand description
A container based on Sparse Set, that stores a set of items and provides a way to efficiently access them by a generated key.
Usage-wise it works similarly to an array, with exceptions that keys stay stable even after removals, and operations like insertions and removals have slight overhead. Also, it has higher memory consumption, since it needs to store additional data for each element.
Good for cache efficiency. Doesn’t require any hashing. Can’t be serialized.
Insertions are O(1) amortized. Removals are O(1) if the order of elements can be changed, O(n) if the order must be preserved. Accessing elements is O(1).
Extra memory consumption for each value is 4 * sizeof(usize) bytes on top of the size of the value (e.g. 32 bytes per element on 64-bit systems). The memory consumption will also grow by 2 * sizeof(usize) per 2^(sizeof(usize) * 8) elements removed (e.g. 16 bytes per 18446744073709551616 elements removed on 64-bit systems).
ZST (zero-sized types) are not supported, trying to use them will result in a panic.
Implementations§
Source§impl<T> SparseSet<T>
impl<T> SparseSet<T>
Sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Creates a new SparseSet with allocated memory for the given number of elements.
§Panics
- Panics if the type
Tis zero-sized. - Panics if the memory allocation fails.
Sourcepub fn push(&mut self, value: T) -> SparseKey
pub fn push(&mut self, value: T) -> SparseKey
Inserts a new value into the set and returns a key that can be used to access it.
This can heap-allocate (if the internal arrays need to grow) but it won’t invalidate any existing keys. If some objects were removed before, it will reclaim the previously freed space.
O(1) amortized time complexity.
§Panics
Panics if a memory allocation fails.
Sourcepub fn swap_remove(&mut self, key: SparseKey) -> Option<T>
pub fn swap_remove(&mut self, key: SparseKey) -> Option<T>
Removes an element from the set using the key, swapping it with the last element. Returns the removed value if it was present in the set.
O(1) time complexity, however changes the order of elements.
§Panics
Can panic if the used key is not from this SparseSet.
Sourcepub fn remove(&mut self, key: SparseKey) -> Option<T>
pub fn remove(&mut self, key: SparseKey) -> Option<T>
Removes an element from the set using the key, keeping the order of elements. Returns the removed value if it was present in the set.
O(n) time complexity, however doesn’t change the order of elements.
§Panics
Can panic if the used key is not from this SparseSet.
Sourcepub fn swap(&mut self, key1: SparseKey, key2: SparseKey)
pub fn swap(&mut self, key1: SparseKey, key2: SparseKey)
Swaps two elements in the set using their keys.
O(1) time complexity.
§Panics
- Panics if any of the keys are not present in the set (were removed)
- Can panic if the used keys are not from this SparseSet.
Sourcepub fn get(&self, key: SparseKey) -> Option<&T>
pub fn get(&self, key: SparseKey) -> Option<&T>
Returns a reference to the value stored at the given key. If the key is not valid, returns None.
O(1) time complexity.
§Panics
Can panic if the used key is not from this SparseSet.
Sourcepub fn get_mut(&mut self, key: SparseKey) -> Option<&mut T>
pub fn get_mut(&mut self, key: SparseKey) -> Option<&mut T>
Returns a mutable reference to the value stored at the given key. If the key is not valid, returns None.
O(1) time complexity.
§Panics
Can panic if the used key is not from this SparseSet.
Sourcepub fn contains(&self, key: SparseKey) -> bool
pub fn contains(&self, key: SparseKey) -> bool
Returns true if the key points to a valid element in the set.
O(1) time complexity.
§Panics
Can panic if the used key is not from this SparseSet.
Sourcepub fn values(&self) -> impl DoubleEndedIterator<Item = &T>
pub fn values(&self) -> impl DoubleEndedIterator<Item = &T>
Returns an iterator over the values of the set.
Sourcepub fn values_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T>
pub fn values_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T>
Returns an iterator over the mutable values of the set.
Sourcepub fn keys(&self) -> impl DoubleEndedIterator<Item = SparseKey> + '_
pub fn keys(&self) -> impl DoubleEndedIterator<Item = SparseKey> + '_
Returns an iterator over the keys of the set.
Sourcepub fn key_values(&self) -> impl DoubleEndedIterator<Item = (SparseKey, &T)>
pub fn key_values(&self) -> impl DoubleEndedIterator<Item = (SparseKey, &T)>
Returns an iterator over the key-value pairs of the set.
Note that if you intend to iterate over key-values in time-critical code, it may be better to instead store the keys in the elements themselves to reduce CPU cache misses.