Struct sparseset::SparseSet

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

An implementation of a sparse set.

A sparse set is a specialized data structure for representing a set of integers. It can be useful in some very narrow and specific cases, namely when the universe of possible values is very large but used very sparingly and the set is iterated often or cleared often.

In this implement the SparseSet can hold an arbitrary value for every integer (key) in the set.

Example

use sparseset::SparseSet;
let mut set = SparseSet::with_capacity(128);
set.insert(42, 3);
set.insert(77, 5);
set.insert(23, 8);

assert_eq!(*set.get(42).unwrap(), 3);

set.remove(42);
assert!(!set.get(42).is_some());

for entry in set {
    println!("- {} => {}", entry.key(), entry.value);
}

Performance

Note that SparseSet is incredibly inefficient in terms of space. The O(1) insertion time assumes space for the element is already allocated. Otherwise, a large key may require a massive reallocation, with no direct relation to the number of elements in the collection. SparseSet should only be seriously considered for small keys.

Runtime complexity

See how the runtime complexity of SparseSet compares to Hash and Btree maps:

	get	insert	remove	iterate	clear
SparseSet	O(1)	O(1)*	O(1)	O(n)	O(1) / O(n)*
HashMap	O(1)~	O(1)~*	O(1)~	N/A	N/A
BTreeMap	O(log n)	O(log n)	O(log n)	N/A	N/A

• Clear is O(1) on simple types and O(n) on types whom implements Drop.
• Iterating is really efficient, its iterating over a dense array. In fact, its even possible to get an (even mutable) slice of the entries in the set.

See http://research.swtch.com/sparse for more details.

Methods

impl<T> SparseSet<T>

pub fn with_capacity(size: usize) -> Self

Creates a SparseSet with the given capacity.

pub fn len(&self) -> usize

pub fn capacity(&self) -> usize

pub fn clear(&mut self)

Clears the SparseSet in O(1) for simple T and O(n) if T implements Drop.

pub fn get(&self, key: usize) -> Option<&T>

Returns a reference to the value corresponding to the given key in O(1).

pub fn get_mut(&mut self, key: usize) -> Option<&mut T>

Returns a mutable reference to the value corresponding to the given key in O(1).

pub fn contains(&self, key: usize) -> bool

Test if the given key is contained in the set in O(1).

pub fn insert(&mut self, key: usize, value: T) -> bool

Insert in the set a value for the given key in O(1).

• returns true if the key was set.
• returns false if the key was already set.

If the key was already set, the previous value is overridden.

pub fn remove(&mut self, key: usize) -> Option<T>

Removes the given key in O(1). Returns the removed value or None if key not found.

Trait Implementations

impl<T> IntoIterator for SparseSet<T>

Move into an interator, consuming the SparseSet.

type Item = Entry<T>

The type of the elements being iterated over.

type IntoIter = IntoIter<Self::Item>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a SparseSet<T>

An interator over the elements of the SparseSet.

type Item = &'a Entry<T>

The type of the elements being iterated over.

type IntoIter = Iter<'a, Entry<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut SparseSet<T>

An interator over mutable elements of the SparseSet.

type Item = &'a mut Entry<T>

The type of the elements being iterated over.

type IntoIter = IterMut<'a, Entry<T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Deref for SparseSet<T>

Deref to a slice.

type Target = [Entry<T>]

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T> DerefMut for SparseSet<T>

Deref to a mutable slice.

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.