Struct tinyset::u64set::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 integers, while not being bad at storing large integers (i.e. about half the size of a large fnv::HashSet, for small sets of large integers about five times smaller than fnv::HashSet. For small numbers, Set64 is even more compact.

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

A Set64 is somewhat complicated in its data format, because it has 8 possibilities, and which of those formats it takes depends on the largest value stored and how many values are stored. Note that the size of value is defined in terms of the u64 that the element can be converted into.

1. If there are 22 or less items that are less than 255, then the set is stored as an array of u8 with a single byte indicating how many elements there are. Search and addition is linear in the number of elements, and way faster than O(1) operations would be. No heap storage is used.
2. If there are 11 or less items that are less than 2^16-1, then the set is stored as an array of u16 with a single byte indicating how many elements there are. Search and addition is linear in the number of elements, and way faster than O(1) operations would be. No heap storage is used.
3. If there are 5 or less items that are less than 2^32-1, then the set is stored as an array of u32 with a single byte indicating how many elements there are. Search and addition is linear in the number of elements, and way faster than O(1) operations would be. No heap storage is used.
4. If there are 2 or less items that are less than 2^64-1, then the set is stored as an array of u64 with a single byte indicating how many elements there are. Search and addition is linear in the number of elements, and way faster than O(1) operations would be. No heap storage is used.
5. If there are many items that are less than 255, then the set is stored on the heap as a Robin Hood hash set of u8 values.
6. If there are many items that are less than 2^16-1, then the set is stored on the heap as a Robin Hood hash set of u16 values.
7. If there are many items that are less than 2^32-1, then the set is stored on the heap as a Robin Hood hash set of u32 values.
8. If there are many large items, then the set is stored on the heap as a Robin Hood hash set of u64 values.

Methods

impl<T: Fits64> Set64<T>

pub fn default() -> Self

Creates an empty set..

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 with_max_and_capacity(max: T, cap: usize) -> Self

Creates an empty set with the specified capacity.

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the set. The collection may reserve more space to avoid frequent reallocations.

pub fn reserve_with_max(&mut self, max: T, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the set, with maximum value of max. The collection may reserve more space to avoid frequent reallocations.

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.

Important traits for Iter64<'a, T>

impl<'a, T: Fits64> Iterator for Iter64<'a, T> type Item = T;

pub fn iter(&self) -> Iter64<T>

Iterate

Important traits for Drain64<T>

impl<T: Fits64> Iterator for Drain64<T> type Item = T;

pub fn drain(&mut self) -> Drain64<T>

Drain

Trait Implementations

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());

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

#[must_use]

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

This method tests for !=.

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<'a, T: Fits64> IntoIterator for &'a Set64<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = Iter64<'a, T>

Which kind of iterator are we turning this into?

Important traits for Iter64<'a, T>

impl<'a, T: Fits64> Iterator for Iter64<'a, T> type Item = T;

fn into_iter(self) -> Iter64<'a, T>

Creates an iterator from a value.

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

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

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

Formats the value using the given formatter.

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

type Output = Set64<T>

The resulting type after applying the - operator.

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());

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

type Output = Set64<T>

The resulting type after applying the | operator.

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());

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

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

Creates a value from an iterator.