Struct tinyset::set64::Set64

pub struct Set64<T: Fits64>(_, _);

A set type that can store any type that fits in a u64. This set type is very space-efficient in storing small or closely spaced integers, while not being bad at storing large integers.

Major caveat The Set64 type defines iterators (drain() and iter()) that iterate over T rather than &T. This is a break with standard libray convention, and can be annoying if you are translating code from HashSet to Set64. The motivation for this is several-fold:

1. Set64 does not store T directly in its data structures (which would waste space), so there is no reference to the data to take. This does not make it impossible, but does mean we would have to fabricate a T and return a reference to it, which is awkward and ugly.

2. There is no inefficiency involved in returning T, since it is necessarily no larger than a pointer.

Examples

use tinyset::Set64;

let a: Set64<char> = "Hello world".chars().collect();

for x in "Hello world".chars() {
    assert!(a.contains(&x));
}
for x in a {
    assert!("Hello world".contains(x));
}

Storage details

Internally a Set64 is identical to a SetU64, so read there for details. In short, small sets are the size of a pointer with no heap storage. Densely packed sets are around a bit per member. Intermediate sets have intermediate storage. The worst case scenario is large integers widely spaced apart, in which case the storage is similar to a std::collections::HashSet.

Implementations

impl<T: Fits64> Set64<T>

pub fn is_empty(&self) -> bool

Returns true if the set is empty

impl<T: Fits64> Set64<T>

pub fn new() -> Self

Creates an empty set..

pub fn with_capacity(_cap: usize) -> Self

Creates an empty set with the specified capacity.

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

Adds a value to the set.

If the set did not have this value present, true is returned.

If the set did have this value present, false is returned.

pub fn len(&self) -> usize

Returns the number of elements in the set.

pub fn contains<R: Borrow<T>>(&self, value: R) -> bool

Returns true if the set contains a value.

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

Removes an element, and returns true if that element was present.

pub fn iter<'a>(&'a self) -> impl Iterator<Item = T> + 'a

Iterate

pub fn drain<'a>(&'a mut self) -> impl Iterator<Item = T> + 'a

Drain

Trait Implementations

impl<'a, 'b, T: Fits64> BitOr<&'b Set64<T>> for &'a Set64<T>

fn bitor(self, rhs: &Set64<T>) -> Set64<T>

Returns the union of self and rhs as a new Set64<T>.

Examples

use tinyset::Set64;

let a: Set64<u32> = vec![1, 2, 3].into_iter().collect();
let b: Set64<u32> = vec![3, 4, 5].into_iter().collect();

let set = &a | &b;

let mut i = 0;
let expected = [1, 2, 3, 4, 5];
for x in set {
    assert!(expected.contains(&x));
    i += 1;
}
assert_eq!(i, expected.len());

type Output = Set64<T>

The resulting type after applying the | operator.

impl<T: Clone + Fits64> Clone for Set64<T>

fn clone(&self) -> Set64<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Fits64> Debug for Set64<T>

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

Formats the value using the given formatter.

impl<T: Fits64> Default for Set64<T>

fn default() -> Self

Creates an empty set..

impl<T: Fits64> Extend<T> for Set64<T>

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

Adds a bunch of elements to the set

Examples

use tinyset::Set64;

let mut a: Set64<u32> = vec![1, 2, 3].into_iter().collect();
a.extend(vec![3, 4, 5]);

let mut i = 0;
let expected = [1, 2, 3, 4, 5];
for x in a {
    assert!(expected.contains(&x));
    i += 1;
}
assert_eq!(i, expected.len());

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: Fits64> FromIterator<T> for Set64<T>

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

Creates a value from an iterator.

impl<T: Fits64> Hash for Set64<T>

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, 

Feeds a slice of this type into the given Hasher.

impl<T: Fits64> IntoIterator for Set64<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.

impl<T: Fits64> PartialEq<Set64<T>> for Set64<T>

fn eq(&self, other: &Set64<T>) -> 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 !=.

impl<'a, 'b, T: Fits64> Sub<&'b Set64<T>> for &'a Set64<T>

fn sub(self, rhs: &Set64<T>) -> Set64<T>

Returns the difference of self and rhs as a new Set64<T>.

Examples

use tinyset::Set64;

let a: Set64<u32> = vec![1, 2, 3].into_iter().collect();
let b: Set64<u32> = vec![3, 4, 5].into_iter().collect();

let set = &a - &b;

let mut i = 0;
let expected = [1, 2];
for x in set {
    assert!(expected.contains(&x));
    i += 1;
}
assert_eq!(i, expected.len());

type Output = Set64<T>

The resulting type after applying the - operator.

impl<T: Fits64> Eq for Set64<T>