Struct vec_collections::VecSet

pub struct VecSet<A: Array>(_);

A set backed by a SmallVec of elements.

A the underlying storage. This must be an array. The size of this array is the maximum size this collection can hold without allocating. VecSet is just a wrapper around a SmallVec, so it does not have additional memory overhead.

Sets support comparison operations ( is_disjoint, is_subset, is_superset ) and set combine operations ( bitand, bitor, bitxor, sub ). They also support in place operations ( bitand_assign, bitor_assign, bitxor_assign, sub_assign ) that will try to avoid allocations.

Creation

The best way to create a VecSet is to use FromIterator, via collect.

use vec_collections::VecSet;
let a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate

General usage

use vec_collections::VecSet;
let a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate
let b: VecSet<[u32; 2]> = (4..6).collect(); // does not allocate
println!("{}", a.is_disjoint(&b)); // true
let c = &a | &b; // underlying smallvec will spill over to the heap
println!("{}", c.contains(&5)); // true

In place operations

use vec_collections::VecSet;
let mut a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate
let b: VecSet<[u32; 4]> = (2..6).collect(); // does not allocate
a &= b; // in place intersection, will yield 2..4, will not allocate
println!("{}", a.contains(&3)); // true

Accessing the elements as a slice

Since a VecSet is a succinct collection, you can get a reference to the contents as a slice.

Example: choosing a random element

use vec_collections::VecSet;
use rand::seq::SliceRandom;
let mut a: VecSet<[u32; 4]> = (0..4).collect(); // does not allocate
let mut rng = rand::thread_rng();
let e = a.as_ref().choose(&mut rng).unwrap();
println!("{}", e);

Implementations

impl<A: Array> VecSet<A>

pub fn single(value: A::Item) -> Self

A set with a single element.

pub fn empty() -> Self

The empty set.

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

An iterator that returns references to the items of this set in sorted order

pub fn len(&self) -> usize

The number of elements in the set.

pub fn shrink_to_fit(&mut self)

Shrink the underlying SmallVec to fit.

pub fn is_empty(&self) -> bool

true if the set is empty.

pub fn into_inner(self) -> SmallVec<A>

Returns the wrapped SmallVec.

impl<A: Array> VecSet<A> where
    A::Item: Ord, 

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

insert an element.

The time complexity of this is O(N), so building a large set using single element inserts will be slow! Prefer using from_iter when building a large VecSet from elements.

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

Remove an element.

The time complexity of this is O(N), so removing many elements using single element removes inserts will be slow! Prefer using retain when removing a large number of elements.

pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, f: F)

Retain all elements matching a predicate.

pub fn is_disjoint<B: Array<Item = A::Item>>(&self, that: &VecSet<B>) -> bool

true if this set has no common elements with another set.

pub fn is_subset<B: Array<Item = A::Item>>(&self, that: &VecSet<B>) -> bool

true if this set is a subset of another set.

A set is considered to be a subset of itself.

pub fn is_superset<B: Array<Item = A::Item>>(&self, that: &VecSet<B>) -> bool

true if this set is a superset of another set.

A set is considered to be a superset of itself.

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

true if this set contains the item.

Time complexity is O(log N). Binary search.

Trait Implementations

impl<A: Array> AsRef<[<A as Array>::Item]> for VecSet<A>

fn as_ref(&self) -> &[A::Item]

Performs the conversion.

impl<T: Ord + Clone, Arr: Array<Item = T>, B: Array<Item = T>> BitAnd<&'_ VecSet<B>> for &VecSet<Arr>

type Output = VecSet<Arr>

The resulting type after applying the & operator.

fn bitand(self, that: &VecSet<B>) -> Self::Output

Performs the & operation.

impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> BitAndAssign<VecSet<B>> for VecSet<A>

fn bitand_assign(&mut self, that: VecSet<B>)

Performs the &= operation.

impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitOr<&'_ VecSet<B>> for &VecSet<A>

type Output = VecSet<A>

The resulting type after applying the | operator.

fn bitor(self, that: &VecSet<B>) -> Self::Output

Performs the | operation.

impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> BitOrAssign<VecSet<B>> for VecSet<A>

fn bitor_assign(&mut self, that: VecSet<B>)

Performs the |= operation.

impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> BitXor<&'_ VecSet<B>> for &VecSet<A>

type Output = VecSet<A>

The resulting type after applying the ^ operator.

fn bitxor(self, that: &VecSet<B>) -> Self::Output

Performs the ^ operation.

impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> BitXorAssign<VecSet<B>> for VecSet<A>

fn bitxor_assign(&mut self, that: VecSet<B>)

Performs the ^= operation.

impl<T: Clone, A: Array<Item = T>> Clone for VecSet<A>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, A: Array<Item = T>> Debug for VecSet<A>

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

Formats the value using the given formatter.

impl<A: Default + Array> Default for VecSet<A>

fn default() -> VecSet<A>

Returns the "default value" for a type.

impl<'de, A: Array> Deserialize<'de> for VecSet<A> where
    A::Item: Deserialize<'de> + Ord, 

fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error>

Deserialize this value from the given Serde deserializer.

impl<T: Eq, A: Array<Item = T>> Eq for VecSet<A>

impl<T: Ord, A: Array<Item = T>> Extend<T> for VecSet<A>

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

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

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

Extends a collection with exactly one element.

pub 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: Ord, A: Array<Item = T>> From<BTreeSet<T>> for VecSet<A>

Provides a way to create a VecSet from a BTreeSet without having to sort again

fn from(value: BTreeSet<T>) -> Self

Performs the conversion.

impl<T: Ord, A: Array<Item = T>> From<Vec<T, Global>> for VecSet<A>

fn from(vec: Vec<T>) -> Self

Performs the conversion.

impl<A: Array> From<VecMap<A>> for VecSet<A>

fn from(value: VecMap<A>) -> Self

Performs the conversion.

impl<T: Ord, A: Array<Item = T>> FromIterator<T> for VecSet<A>

Builds the set from an iterator.

Uses a heuristic to deduplicate while building the set, so the intermediate storage will never be more than twice the size of the resulting set. This is the most efficient way to build a large VecSet, significantly more efficient than single element insertion.

Worst case performance is O(log(n)^2 * n), but performance for already partially sorted collections will be significantly better. For a fully sorted collection, performance will be O(n).

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

Creates a value from an iterator.

impl<T: Hash, A: Array<Item = T>> Hash for VecSet<A>

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

impl<A: Array> Into<SmallVec<A>> for VecSet<A>

fn into(self) -> SmallVec<A>

Performs the conversion.

impl<A: Array> Into<Vec<<A as Array>::Item, Global>> for VecSet<A>

fn into(self) -> Vec<A::Item>

Performs the conversion.

impl<'a, A: Array> IntoIterator for &'a VecSet<A>

type Item = &'a A::Item

The type of the elements being iterated over.

type IntoIter = VecSetIter<Iter<'a, A::Item>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<A: Array> IntoIterator for VecSet<A>

type Item = A::Item

The type of the elements being iterated over.

type IntoIter = VecSetIter<IntoIter<A>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Ord, A: Array<Item = T>> Ord for VecSet<A>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

#[must_use]pub fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]pub fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]pub fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl<T: PartialEq, A: Array<Item = T>> PartialEq<VecSet<A>> for VecSet<A>

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

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

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: PartialOrd, A: Array<Item = T>> PartialOrd<VecSet<A>> for VecSet<A>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]pub fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]pub fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]pub fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<A: Array> Serialize for VecSet<A> where
    A::Item: Serialize, 

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serialize this value into the given Serde serializer.

impl<T: Ord + Clone, A: Array<Item = T>, B: Array<Item = T>> Sub<&'_ VecSet<B>> for &VecSet<A>

type Output = VecSet<A>

The resulting type after applying the - operator.

fn sub(self, that: &VecSet<B>) -> Self::Output

Performs the - operation.

impl<T: Ord, A: Array<Item = T>, B: Array<Item = T>> SubAssign<VecSet<B>> for VecSet<A>

fn sub_assign(&mut self, that: VecSet<B>)

Performs the -= operation.