Struct SmallSet 

pub struct SmallSet<T, const N: usize> { /* private fields */ }

A set that lives on the stack for N items, then automatically spills to the heap.

Implementation Details

This is a wrapper around SmallMap<T, (), N>. Since () is a zero-sized type in Rust, this wrapper has zero memory overhead compared to a raw set implementation.

• Stack State: Zero allocations. Extremely fast FNV hashing.
• Heap State: Standard HashMap performance.
• Spill: Zero-allocation move. Keys are moved, not cloned.

Implementations

impl<T, const N: usize> SmallSet<T, N>

where T: Eq + Hash,

pub fn new() -> Self

Creates a new empty set.

The set initially lives on the stack.

pub fn is_on_stack(&self) -> bool

Returns true if the set is currently storing data on the stack.

pub fn len(&self) -> usize

Returns the number of elements in the set.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

pub fn clear(&mut self)

Clears the set, removing all values.

This keeps the allocated memory (if on heap) for reuse.

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

Adds a value to the set.

Returns true if the value was newly inserted. Returns false if the value was already present.

If the stack capacity N is exceeded, this triggers a spill to the heap.

pub fn contains<Q>(&self, value: &Q) -> bool

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if the set contains a value.

This method is generic over Q to allow looking up String keys with &str.

pub fn remove<Q>(&mut self, value: &Q) -> bool

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes a value from the set. Returns true if the value was present.

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

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

Retains only the elements specified by the predicate.

In other words, remove all elements e such that f(&e) returns false. This method operates in O(n) time.

pub fn iter(&self) -> SetRefIter<'_, T>

Returns an iterator visiting all elements in arbitrary order.

pub fn difference<'a, S>(&'a self, other: &'a S) -> impl Iterator<Item = &'a T>

where S: AnySet<T>,

Visits the values representing the difference, i.e., the values that are in self but not in other.

other can be any collection implementing AnySet (SmallSet, HashSet, BTreeSet).

pub fn intersection<'a, S>( &'a self, other: &'a S, ) -> impl Iterator<Item = &'a T>

where S: AnySet<T>,

Visits the values representing the intersection, i.e., the values that are both in self and other.

pub fn union<'a, I>(&'a self, other: I) -> impl Iterator<Item = &'a T>

where I: IntoIterator<Item = &'a T>, I::IntoIter: 'a,

Visits the values representing the union, i.e., all the values in self or other, without duplicates.

other can be any iterator yielding &T.

pub fn is_disjoint<S>(&self, other: &S) -> bool

where S: AnySet<T>,

Returns true if self has no elements in common with other.

pub fn is_subset<S>(&self, other: &S) -> bool

where S: AnySet<T>,

Returns true if self is a subset of other.

other must be a Set (implement AnySet) to ensure O(1) lookups.

pub fn is_superset<'a, I>(&self, other: I) -> bool

where T: 'a, I: IntoIterator<Item = &'a T>,

Returns true if self is a superset of other.

other can be any iterator. We must ensure T lives as long as the iterator 'a.

pub fn symmetric_difference<'a>( &'a self, other: &'a SmallSet<T, N>, ) -> impl Iterator<Item = &'a T>

Visits the values representing the symmetric difference, i.e., values that are in self or other but not in both.

Trait Implementations

impl<T, const N: usize> AnySet<T> for SmallSet<T, N>

where T: Eq + Hash,

fn contains(&self, value: &T) -> bool

Returns true if the collection contains the value.

fn len(&self) -> usize

Returns the number of elements in the collection.

fn is_empty(&self) -> bool

Returns true if the collection is empty.

impl<T, const N: usize> Clone for SmallSet<T, N>

where T: Eq + Hash + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Eq + Hash, const N: usize> Debug for SmallSet<T, N>

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

Formats the value using the given formatter.

impl<T: Eq + Hash, const N: usize> Default for SmallSet<T, N>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T, const N: usize> Extend<&'a T> for SmallSet<T, N>

where T: 'a + Eq + Hash + Clone + Copy,

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, const N: usize> Extend<T> for SmallSet<T, N>

where T: Eq + Hash + Clone,

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Eq + Hash, const N: usize> FromIterator<T> for SmallSet<T, N>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, T, const N: usize> IntoIterator for &'a SmallSet<T, N>

where T: Eq + Hash,

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = SetRefIter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Eq + Hash, const N: usize> IntoIterator for SmallSet<T, N>

type Item = T

The type of the elements being iterated over.

type IntoIter = SmallSetIntoIter<T, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const N: usize, S> PartialEq<S> for SmallSet<T, N>

where T: Eq + Hash + Clone, S: AnySet<T>,

fn eq(&self, other: &S) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, const N: usize> Eq for SmallSet<T, N>

where T: Eq + Hash + Clone,