Crate david_set [−] [src]
david-set contains a few collections that are optimized to scale in size well for small numbers of elements, while still scaling well in time (and size) for numbers of elements. We have two set types:
Set
is basically interchangeable withHashSet
, although it does require that its elements implement theCopy
trait, since otherwise I would have to learn to write correctunsafe
code, which would be scary.CastSet
is places a stronger requirement on its elements, which must have traitCast
. This is intended for elements that areCopy
, can be cheaply converted tousize
, and are sufficiently evenly distributed that they do not require real hashing. Basically, this is suitable if you want to store a set of indices into an array. All the basic integer types should satisfy traitCast
. Oh, and this set also requires that one value of your type is "invalid". For the unsigned integer types, we take their maximum value to mean invalid. This constraint allows us to save a bit more space.
Both of these set types will do no heap allocation for small sets
of small elements. CastSet
will store up to 16 bytes of
elements before doing any heap allocation, while Set
stores sets
up to size 8 without allocation. Both sets are typically faster
than HashSet
by a factor of around two, although for sets with
more than 8 elements Set
is in fact identical to HashSet
in
performance.
Examples
use david_set::Set; let mut s: Set<usize> = Set::new(); s.insert(1); assert!(s.contains(&1));
use david_set::CastSet; let mut s: CastSet<usize> = CastSet::new(); s.insert(1); assert!(s.contains(&1));
Structs
CastSet |
A set implemented for types that can be cast to usize |
Set |
A set that is a |
VecSet |
A set that is stored in a Vec |
Constants
CAPACITY |
The number of elements stored in an array before moving up to the
|
Traits
Cast |
Trait for any type that can be converted to a |