Struct SmallSet

pub struct SmallSet<A: Array>
where
    A::Item: PartialEq + Eq,
{ /* private fields */ }

A SmallSet is an unordered set of elements. It is designed to work best for very small sets (no more than ten or so elements). In order to support small sets very efficiently, it stores elements in a simple unordered array. When the set is smaller than the size of the array A, all elements are stored inline, without heap allocation. This is accomplished by using a smallvec::SmallVec.

The insert, remove, and query methods on SmallSet have O(n) time complexity in the current set size: they perform a linear scan to determine if the element in question is present. This is inefficient for large sets, but fast and cache-friendly for small sets.

Example usage:

use smallset::SmallSet;

// `s` and its elements will be completely stack-allocated in this example.
let mut s: SmallSet<[u32; 4]> = SmallSet::new();
s.insert(1);
s.insert(2);
s.insert(3);
assert!(s.len() == 3);
assert!(s.contains(&1));

Implementations

impl<A: Array> SmallSet<A>

where A::Item: PartialEq + Eq,

pub fn new() -> SmallSet<A>

Creates a new, empty SmallSet.

pub fn insert(&mut self, elem: A::Item) -> bool

Inserts elem into the set if not yet present. Returns true if the set did not have this element present, or false if it already had this element present.

pub fn remove(&mut self, elem: &A::Item) -> bool

Removes elem from the set. Returns true if the element was removed, or false if it was not found.

pub fn contains(&self, elem: &A::Item) -> bool

Tests whether elem is present. Returns true if it is present, or false if not.

pub fn iter(&self) -> Iter<'_, A::Item>

Returns an iterator over the set elements. Elements will be returned in an arbitrary (unsorted) order.

pub fn len(&self) -> usize

Returns the current length of the set.

pub fn clear(&mut self)

Clears the set.

Trait Implementations

impl<A: Array> Clone for SmallSet<A>

where A::Item: PartialEq + Eq + Clone,

fn clone(&self) -> SmallSet<A>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<A: Array> Debug for SmallSet<A>

where A::Item: PartialEq + Eq + Debug,

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

Formats the value using the given formatter.

impl<A: Array> FromIterator<<A as Array>::Item> for SmallSet<A>

where A::Item: PartialEq + Eq,

fn from_iter<T>(iter: T) -> Self

where T: IntoIterator<Item = A::Item>,

Creates a value from an iterator.