Struct more_collections::small_set::SmallSet

pub struct SmallSet<T, const C: usize, S = RandomState> { /* private fields */ }

A set-like container that can store a specified number of elements inline.

SmallSet shares most of its API with, and behaves like, IndexSet. It can store a limited amount of data inline, backed by SmallVec. If the data exceeds the limit C, SmallSet will move all its data over to the heap in the form of an IndexSet. For performance reasons, transitions between heap and inline storage should generally be avoided.

The SmallSet datastructure is meant for situations where the data does not exceed C most of the time but it still needs to support cases where the data does exceed C.

Example

use more_collections::SmallSet;

let mut set = SmallSet::<usize, 3>::new();
// The set can hold up to three items inline
set.insert(0);
set.insert(1);
set.insert(2);
assert_eq!(3, set.len());
assert!(set.is_inline());

// Adding the fourth element will move the set to the heap
set.insert(3);
assert_eq!(4, set.len());
assert!(!set.is_inline());

Implementations

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

pub fn new() -> Self

Create a new set.

impl<T, const C: usize, S> SmallSet<T, C, S>

pub fn len(&self) -> usize

The number of values stored in the set.

pub fn is_empty(&self) -> bool

Returns true if the set is empty.

pub const fn inline_capacity(&self) -> usize

The memory capacity that will be allocated inline. If the nubmer of values exceeds the inline capacity, the set will move to the heap.

pub const fn is_inline(&self) -> bool

Is the data contained by this set stored inline (true) or on the heap (false).

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

Returns an iterator over the values in insertion order.

impl<T, const C: usize, S> SmallSet<T, C, S>

where T: Hash + Eq, S: BuildHasher + Default,

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

Inserts the specified value into this set.

If an equivalent item already exists in the set, it returns false leaving the original value in the set and without altering its insertion order. Otherwise, it inserts the new item and returns true.

If a new value is added that causes the size of the SmallSet to exceed the inline capacity, all existing data and the new value is moved to the heap.

Computational complexity:

• inline: O(n)
• heap: O(1)

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

Inserts the specified value into this set, and get their index.

If an equivalent item already exists in the set, it returns the index of the existing item and false, leaving the original value in the set and without altering its insertion order. Otherwise, it inserts the new item and returns the index of the inserted item and true.

If a new value is added that causes the size of the SmallSet to exceed the inline capacity, all existing data and the new value is moved to the heap.

Computational complexity:

• inline: O(n)
• heap: O(1)

impl<T, const C: usize, S> SmallSet<T, C, S>

where T: Hash + Eq, S: BuildHasher,

pub const fn from_keys(map: SmallMap<T, (), C, S>) -> Self

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

Get a value by index, if it is present, else None.

Computational complexity: O(1)

pub fn get_index_of<Q>(&self, key: &Q) -> Option<usize>

where Q: Hash + Equivalent<T> + ?Sized,

Return the item index, if it exists in the set, else None.

Computational complexity:

• inline: O(n)
• heap: O(1)

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

where Q: Hash + Equivalent<T> + ?Sized,

Remove the key-value pair equivalent to key and return its value.

NOTE: This is equivalent to .swap_remove(key), if you need to preserve the order of the keys in the map, use .shift_remove(key) instead.

Computes in O(1) time (average).

pub fn difference<'a, const C2: usize, S2>( &'a self, other: &'a SmallSet<T, C2, S2>, ) -> Difference<'a, T, C2, S2>

where S2: BuildHasher,

Return an iterator over the values that are in self but not other.

Values are produced in the same order that they appear in self.

pub fn symmetric_difference<'a, const C2: usize, S2>( &'a self, other: &'a SmallSet<T, C2, S2>, ) -> SymmetricDifference<'a, T, C, S, C2, S2>

where S2: BuildHasher,

Return an iterator over the values that are in self or other, but not in both.

Values from self are produced in their original order, followed by values from other in their original order.

pub fn intersection<'a, const C2: usize, S2>( &'a self, other: &'a SmallSet<T, C2, S2>, ) -> Intersection<'a, T, C2, S2>

where S2: BuildHasher,

Return an iterator over the values that are in both self and other.

Values are produced in the same order that they appear in self.

pub fn union<'a, const C2: usize, S2>( &'a self, other: &'a SmallSet<T, C2, S2>, ) -> Union<'a, T, C, S>

where S2: BuildHasher,

Return an iterator over all values that are in self or other.

Values from self are produced in their original order, followed by values that are unique to other in their original order.

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

where Q: Hash + Equivalent<T> + ?Sized,

Return true if an equivalent to value exists in the set.

Computational complexity:

• inline: O(n)
• heap: O(1)

Trait Implementations

impl<T: Clone, const C: usize, S: Clone> Clone for SmallSet<T, C, S>

fn clone(&self) -> SmallSet<T, C, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T, const C: usize, S> Debug for SmallSet<T, C, S>

where T: Hash + Eq + Debug,

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

Formats the value using the given formatter.

impl<T: Default, const C: usize, S: Default> Default for SmallSet<T, C, S>

fn default() -> SmallSet<T, C, S>

Returns the “default value” for a type.

impl<T, const C: usize, S> FromIterator<T> for SmallSet<T, C, S>

where T: Hash + Eq, S: BuildHasher + Default,

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

Creates a value from an iterator.

impl<T, const C: usize, S> Hash for SmallSet<T, C, S>

where T: Hash + Eq,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

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

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = &'a T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const C: usize, S> IntoIterator for SmallSet<T, C, S>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, C>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

where T: Hash + Eq,

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<T, const C: usize, S> Eq for SmallSet<T, C, S>

where T: Hash + Eq,