Struct SmallSet

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

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§

Source§

impl<A: Array> SmallSet<A>
where A::Item: PartialEq + Eq,

Source

pub fn new() -> SmallSet<A>

Creates a new, empty SmallSet.

Source

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.

Source

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.

Source

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

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

Source

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

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

Source

pub fn len(&self) -> usize

Returns the current length of the set.

Source

pub fn clear(&mut self)

Clears the set.

Trait Implementations§

Source§

impl<A: Array> Clone for SmallSet<A>
where A::Item: PartialEq + Eq + Clone,

Source§

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

Returns a copy of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<A: Array> Debug for SmallSet<A>
where A::Item: PartialEq + Eq + Debug,

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<A: Array> FromIterator<<A as Array>::Item> for SmallSet<A>
where A::Item: PartialEq + Eq,

Source§

fn from_iter<T>(iter: T) -> Self
where T: IntoIterator<Item = A::Item>,

Creates a value from an iterator. Read more

Auto Trait Implementations§

§

impl<A> Freeze for SmallSet<A>
where A: Freeze,

§

impl<A> RefUnwindSafe for SmallSet<A>

§

impl<A> Send for SmallSet<A>
where <A as Array>::Item: Send,

§

impl<A> Sync for SmallSet<A>
where A: Sync,

§

impl<A> Unpin for SmallSet<A>
where A: Unpin,

§

impl<A> UnwindSafe for SmallSet<A>
where A: UnwindSafe, <A as Array>::Item: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.