[−][src]Struct tinyset::u64set::Set64
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:
-
Set64
does not storeT
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 aT
and return a reference to it, which is awkward and ugly. -
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.
- 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 thanO(1)
operations would be. No heap storage is used. - 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 thanO(1)
operations would be. No heap storage is used. - 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 thanO(1)
operations would be. No heap storage is used. - 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 thanO(1)
operations would be. No heap storage is used. - 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. - 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. - 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. - 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>
[src]
pub fn default() -> Self
[src]
Creates an empty set..
pub fn new() -> Self
[src]
Creates an empty set..
pub fn with_capacity(cap: usize) -> Self
[src]
Creates an empty set with the specified capacity.
pub fn with_max_and_capacity(max: T, cap: usize) -> Self
[src]
Creates an empty set with the specified capacity.
pub fn reserve(&mut self, additional: usize)
[src]
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)
[src]
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
[src]
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
[src]
Returns the number of elements in the set.
pub fn contains<R: Borrow<T>>(&self, value: R) -> bool
[src]
Returns true if the set contains a value.
pub fn remove(&mut self, value: &T) -> bool
[src]
Removes an element, and returns true if that element was present.
ⓘImportant traits for Iter64<'a, T>pub fn iter(&self) -> Iter64<T>
[src]
Iterate
ⓘImportant traits for Drain64<T>pub fn drain(&mut self) -> Drain64<T>
[src]
Drain
Trait Implementations
impl<T: Fits64> Eq for Set64<T>
[src]
impl<T: Clone + Fits64> Clone for Set64<T>
[src]
fn clone(&self) -> Set64<T>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<T: Fits64> PartialEq<Set64<T>> for Set64<T>
[src]
fn eq(&self, other: &Set64<T>) -> bool
[src]
#[must_use]
fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
This method tests for !=
.
impl<T: Fits64> Extend<T> for Set64<T>
[src]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
[src]
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<'a, T: Fits64> IntoIterator for &'a Set64<T>
[src]
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>fn into_iter(self) -> Iter64<'a, T>
[src]
impl<T: Debug + Fits64> Debug for Set64<T>
[src]
impl<'a, 'b, T: Fits64> Sub<&'b Set64<T>> for &'a Set64<T>
[src]
type Output = Set64<T>
The resulting type after applying the -
operator.
fn sub(self, rhs: &Set64<T>) -> Set64<T>
[src]
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<T: Fits64> Hash for Set64<T>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
Feeds a slice of this type into the given [Hasher
]. Read more
impl<'a, 'b, T: Fits64> BitOr<&'b Set64<T>> for &'a Set64<T>
[src]
type Output = Set64<T>
The resulting type after applying the |
operator.
fn bitor(self, rhs: &Set64<T>) -> Set64<T>
[src]
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> FromIterator<T> for Set64<T>
[src]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
[src]
Auto Trait Implementations
Blanket Implementations
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,