Struct SparseSet 

pub struct SparseSet<K, H = StdHash, E = StdEq, P = PowerOfTwo<2>, S = Medium> { /* private fields */ }

A hash set that trades a little insert speed for low memory use.

Type parameters match crate::SparseMap without the value type.

Implementations

impl<K> SparseSet<K, StdHash, StdEq, PowerOfTwo<2>, Medium>

pub fn new() -> Self

An empty set with no allocation.

Construction places no bound on K. The Hash and Eq bounds belong to the operations that hash or compare a key.

pub fn with_bucket_count(bucket_count: usize) -> Self

An empty set sized for at least bucket_count buckets.

Panics

Panics when bucket_count exceeds the policy maximum.

pub fn try_with_bucket_count(bucket_count: usize) -> Result<Self, LengthError>

An empty set sized for at least bucket_count buckets, fallibly.

impl<K, B, P, S> SparseSet<K, StdHash<B>, StdEq, P, S>

where K: Eq, B: BuildHasher + Default, P: GrowthPolicy, S: Sparsity, StdHash<B>: HashKey<K>,

pub fn with_hasher_and_bucket_count(bucket_count: usize) -> Self

An empty set that hashes with B and uses policy P and sparsity S.

Panics

Panics when bucket_count exceeds the policy maximum.

impl<K, H, E, P, S> SparseSet<K, H, E, P, S>

where H: HashKey<K> + Clone, E: EqKey<K, K> + Clone, P: GrowthPolicy, S: Sparsity,

pub fn with_parts(bucket_count: usize, hash: H, key_eq: E) -> Self

Build a set from explicit hasher, comparator, policy, and sparsity.

Panics

Panics when bucket_count exceeds the policy maximum.

pub fn len(&self) -> usize

Number of keys.

pub fn is_empty(&self) -> bool

Whether the set holds no keys.

pub fn bucket_count(&self) -> usize

The logical bucket count. Zero for a fresh set.

pub fn max_bucket_count(&self) -> usize

The largest bucket count the set can hold.

pub fn max_size(&self) -> usize

The largest number of keys the set can hold.

pub fn load_factor(&self) -> f32

Ratio of keys to buckets. Zero for an empty set.

pub fn max_load_factor(&self) -> f32

The maximum load factor before a grow.

pub fn set_max_load_factor(&mut self, ml: f32)

Set the maximum load factor, clamped to [0.1, 0.8].

pub fn hash_function(&self) -> &H

The hasher.

pub fn key_eq(&self) -> &E

The key comparator.

pub fn clear(&mut self)

Remove every key. Keeps the bucket count.

pub fn rehash(&mut self, count: usize)

Grow so the set holds at least count buckets.

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

Reserve room for count keys without exceeding the load factor.

pub fn insert(&mut self, key: K) -> bool

Insert key. Returns whether it was newly inserted.

pub fn contains<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

Whether key is present.

pub fn contains_precalc<Q>(&self, key: &Q, hash: usize) -> bool

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

Whether key is present, using a precomputed hash.

pub fn count<Q>(&self, key: &Q) -> usize

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

1 when key is present, 0 otherwise.

pub fn count_precalc<Q>(&self, key: &Q, hash: usize) -> usize

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

1 when key is present, 0 otherwise, using a precomputed hash.

pub fn equal_range<Q>(&self, key: &Q) -> EqualRange<'_, K>

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

The range of keys equal to key.

A set holds at most one key per value, so the range is empty or a single key. The returned iterator yields &K and has length 0 or 1.

pub fn equal_range_precalc<Q>(&self, key: &Q, hash: usize) -> EqualRange<'_, K>

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

The range of keys equal to key, using a precomputed hash.

pub fn get<Q>(&self, key: &Q) -> Option<&K>

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

A reference to the stored key equal to key.

pub fn erase<Q>(&mut self, key: &Q) -> usize

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

Remove key. Returns 1 when erased, 0 otherwise.

pub fn take<Q>(&mut self, key: &Q) -> Option<K>

where K: Borrow<Q>, Q: ?Sized, H: HashKey<Q>, E: EqKey<K, Q>,

Remove and return the stored key equal to key.

pub fn pop_front(&mut self) -> Option<K>

Remove and return the first key in iteration order.

pub fn erase_range(&mut self, skip: usize, count: usize)

Remove count keys starting at iteration index skip.

Erasing leaves a tombstone. The walk is a single forward pass.

pub fn erase_all(&mut self)

Remove every key, leaving tombstones. Keeps the bucket count.

Use SparseSet::clear to also reset the tombstones and counters.

pub fn retain<F>(&mut self, keep: F)

where F: FnMut(&K) -> bool,

Keep only the keys for which keep returns true.

Removed keys become tombstones. Each sparse array is scanned once.

impl<K, H, E, P, S> SparseSet<K, H, E, P, S>

pub fn iter(&self) -> Iter<'_, K>

A forward iterator over keys.

impl<K, H, E, P, S> SparseSet<K, H, E, P, S>

where K: Serialize,

pub fn serialize<Sz: Serializer>(&self, serializer: &mut Sz)

Write the set through serializer in protocol order.

impl<K, H, E, P, S> SparseSet<K, H, E, P, S>

where H: HashKey<K> + Clone, E: EqKey<K, K> + Clone, P: GrowthPolicy, S: Sparsity, K: Serialize + Deserialize,

pub fn deserialize_with<D: Deserializer>( deserializer: &mut D, hash_compatible: bool, hash: H, key_eq: E, ) -> Result<Self, DeserializeError>

Read a set written by SparseSet::serialize.

Trait Implementations

impl<K, H, E, P, S> Clone for SparseSet<K, H, E, P, S>

where K: Clone, H: Clone, E: Clone, P: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, H, E, P, S> Debug for SparseSet<K, H, E, P, S>

where K: Debug,

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

Formats the value using the given formatter.

impl<K, H, E, P, S> Default for SparseSet<K, H, E, P, S>

where H: Default, E: Default, P: GrowthPolicy,

fn default() -> Self

An empty set with default parts and no allocation.

Available when the hasher and comparator are Default and the policy can build a zero-bucket table. Places no bound on K.

impl<K, H, E, P, S> Eq for SparseSet<K, H, E, P, S>

where H: HashKey<K> + Clone, E: EqKey<K, K> + Clone, P: GrowthPolicy, S: Sparsity,

impl<K, H, E, P, S> Extend<K> for SparseSet<K, H, E, P, S>

where H: HashKey<K> + Clone, E: EqKey<K, K> + Clone, P: GrowthPolicy, S: Sparsity,

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

Insert every key from iter. Keys already present are ignored.

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<K, const N: usize> From<[K; N]> for SparseSet<K>

where K: Hash + Eq,

fn from(array: [K; N]) -> Self

Converts to this type from the input type.

impl<K> FromIterator<K> for SparseSet<K>

where K: Hash + Eq,

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

Creates a value from an iterator.

impl<'a, K, H, E, P, S> IntoIterator for &'a SparseSet<K, H, E, P, S>

type Item = &'a K

The type of the elements being iterated over.

type IntoIter = Iter<'a, K>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, H, E, P, S> IntoIterator for SparseSet<K, H, E, P, S>

type Item = K

The type of the elements being iterated over.

type IntoIter = IntoIter<K>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, H, E, P, S> PartialEq for SparseSet<K, H, E, P, S>

where H: HashKey<K> + Clone, E: EqKey<K, K> + Clone, P: GrowthPolicy, S: Sparsity,

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.