Struct SparseSet 

pub struct SparseSet<T> { /* private fields */ }

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

impl<T> SparseSet<T>

pub fn new() -> Self

Creates a new SparseSet. Does not allocate.

Panics

Panics if the type T is zero-sized.

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 T is zero-sized.
• Panics if the new buffer size exceeds isize::MAX bytes.

pub fn from_vec(vec: Vec<T>) -> Self

Creates a new SparseSet<T> from a Vec<T>.

O(n) time complexity.

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the given SparseSet<T>.

O(n) time complexity.

Panics

Panics if the buffer size exceeds isize::MAX bytes.

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 the new buffer size exceeds isize::MAX bytes.

pub fn insert_at_position(&mut self, position: usize, value: T) -> SparseKey

Inserts an element at the specified position in the set shifting all elements after it to the right. Returns the key of the inserted element.

O(n) time complexity.

Panics

Panics if the position is greater than the length of the set.

pub fn resize(&mut self, new_len: usize, value: T)

where T: Clone,

Changes the length of the vector, inserting or removing values at the end as needed.

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.

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.

pub fn swap_remove_by_index(&mut self, index: usize) -> Option<T>

Removes an element by the index from the set, 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

Panics if the index is out of bounds.

pub fn remove_by_index(&mut self, index: usize) -> Option<T>

Removes an element by the index from the set, 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

Panics if the index is out of bounds.

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&T) -> bool,

Retains only the elements specified by the predicate.

Or in other words, remove all elements that don’t satisfy the predicate.

Panics

Panics if the predicate panics.

pub fn clear(&mut self)

Removes all the elements from the set.

O(n) time complexity.

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.

pub fn swap_by_index(&mut self, index1: usize, index2: usize)

Swaps two elements in the set using their positions.

O(1) time complexity.

Panics

• Panics if any of the indices are out of bounds.

pub fn rotate_left(&mut self, start_index: usize, end_index: usize, mid: usize)

Rotate the elements in the range [start_index, end_index) to the left while keeping the keys pointing to the same elements.

O(n) time complexity.

Panics

Panics if the indices are out of bounds or end_index is less than start_index.

pub fn rotate_right(&mut self, start_index: usize, end_index: usize, k: usize)

Rotate the elements in the range [start_index, end_index) to the right while keeping the keys pointing to the same elements.

O(n) time complexity.

Panics

Panics if the indices are out of bounds or end_index is less than start_index.

pub fn extend_with_vec(&mut self, values: Vec<T>)

Extends the set with the given values.

O(n) time complexity, where n is the number of elements to be added.

pub fn into_vec(self) -> Vec<T>

Consumes the set and returns a vec with the values.

O(n) time complexity.

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.

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.

pub fn get_by_index(&self, index: usize) -> Option<&T>

Returns a reference to the element at the specified index.

O(1) time complexity.

pub fn get_by_index_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the element at the specified index.

O(1) time complexity.

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.

pub fn len(&self) -> usize

Returns the number of elements in the set.

O(1) time complexity.

pub fn capacity(&self) -> usize

Returns the number of elements the set can hold without reallocating.

O(1) time complexity.

pub fn is_empty(&self) -> bool

Returns true if the set is empty.

O(1) time complexity.

pub fn values(&self) -> impl DoubleEndedIterator<Item = &T>

Returns an iterator over the values of the set.

pub fn values_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T>

Returns an iterator over the mutable values of the set.

pub fn keys(&self) -> impl DoubleEndedIterator<Item = SparseKey> + '_

Returns an iterator over the keys of the set.

pub fn get_key(&self, index: usize) -> Option<SparseKey>

Returns the key of an element at the given index.

pub fn index(&self, key: SparseKey) -> Option<usize>

Returns the index of an element with 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.

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.

Trait Implementations

impl<T: Clone> Clone for SparseSet<T>

fn clone(&self) -> SparseSet<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.