Struct VecSet

pub struct VecSet<A: Array>(/* private fields */);

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, AbstractVecSet};
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, AbstractVecSet};
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.

impl<A: Array> VecSet<A>

where A::Item: Ord + Clone,

pub fn union(&self, that: &impl AbstractVecSet<A::Item>) -> Self

pub fn intersection(&self, that: &impl AbstractVecSet<A::Item>) -> Self

pub fn symmetric_difference(&self, that: &impl AbstractVecSet<A::Item>) -> Self

pub fn difference(&self, that: &impl AbstractVecSet<A::Item>) -> Self

pub fn union_with(&mut self, that: &impl AbstractVecSet<A::Item>)

pub fn intersection_with(&mut self, that: &impl AbstractVecSet<A::Item>)

pub fn xor_with(&mut self, that: &impl AbstractVecSet<A::Item>)

pub fn difference_with(&mut self, that: &impl AbstractVecSet<A::Item>)

Trait Implementations

impl<A: Array> AbstractVecSet<<A as Array>::Item> for VecSet<A>

where A::Item: Ord,

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

fn is_empty(&self) -> bool

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

fn is_disjoint(&self, that: &impl AbstractVecSet<T>) -> bool

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

fn is_subset(&self, that: &impl AbstractVecSet<T>) -> bool

true if this set is a subset of another set.

fn is_superset(&self, that: &impl AbstractVecSet<T>) -> bool

true if this set is a superset of another set.

fn union<A: Array<Item = T>>(&self, that: &impl AbstractVecSet<T>) -> VecSet<A>

where T: Clone,

fn intersection<A: Array<Item = T>>( &self, that: &impl AbstractVecSet<T>, ) -> VecSet<A>

where T: Clone,

fn symmetric_difference<A: Array<Item = T>>( &self, that: &impl AbstractVecSet<T>, ) -> VecSet<A>

where T: Clone,

fn difference<A: Array<Item = T>>( &self, that: &impl AbstractVecSet<T>, ) -> VecSet<A>

where T: Clone,

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

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

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

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

Converts this type into a shared reference of the (usually inferred) input type.

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

type Output = VecSet<A>

The resulting type after applying the & operator.

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

Performs the & operation.

impl<T: Ord + Clone, 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, 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 + Clone, 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, 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 + Clone, 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: 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.

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: 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.

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: 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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

impl<A: Array> From<VecSet<A>> for Vec<A::Item>

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

Converts to this type from the input type.

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.

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, A: Array> IntoIterator for &'a VecSet<A>

type Item = &'a <A as Array>::Item

The type of the elements being iterated over.

type IntoIter = VecSetIter<Iter<'a, <A as Array>::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 as Array>::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.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

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

fn eq(&self, other: &Self) -> 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: PartialOrd, A: Array<Item = T>> PartialOrd for VecSet<A>

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

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

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

Tests less than (for self and other) and is used by the < operator.

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

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

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

Tests greater than (for self and other) and is used by the > operator.

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

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 + Clone, 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.

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.

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