Struct SparseMap 

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

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

Type parameters:

• K, V: key and value types.
• H: the hasher. Defaults to StdHash, which uses the standard BuildHasher. A hasher yields a usize directly.
• E: the key comparator. Defaults to StdEq.
• P: the growth policy. Defaults to PowerOfTwo with factor 2.
• S: the sparsity level. Defaults to Medium.

Implementations

impl<K, V> SparseMap<K, V, StdHash, StdEq, PowerOfTwo<2>, Medium>

pub fn new() -> Self

An empty map 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 map sized for at least bucket_count buckets.

Panics

Panics when bucket_count exceeds the policy maximum. Use SparseMap::try_with_bucket_count for the fallible form.

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

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

impl<K, V, B, P, S> SparseMap<K, V, 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 map that hashes with B and uses policy P and sparsity S.

Panics

Panics when bucket_count exceeds the policy maximum.

impl<K, V, H, E, P, S> SparseMap<K, V, 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 map from explicit hasher, comparator, policy, and sparsity.

Panics

Panics when bucket_count exceeds the policy maximum.

pub fn try_with_parts( bucket_count: usize, hash: H, key_eq: E, ) -> Result<Self, LengthError>

Build a map fallibly from explicit parts.

pub fn len(&self) -> usize

Number of entries.

pub fn is_empty(&self) -> bool

Whether the map holds no entries.

pub fn max_size(&self) -> usize

The largest number of entries the map can hold.

pub fn bucket_count(&self) -> usize

The logical bucket count. Zero for a fresh map.

pub fn max_bucket_count(&self) -> usize

The largest bucket count the map can hold.

pub fn load_factor(&self) -> f32

Ratio of entries to buckets. Zero for an empty map.

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 entry. Keeps the bucket count.

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

Grow so the map holds at least count buckets.

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

Reserve room for count entries without exceeding the load factor.

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

Insert key with value, keeping the existing value on a collision.

Returns whether a new entry was created. insert never overwrites: when key is already present the stored value stays and the passed value is dropped. To keep the rejected value, use SparseMap::try_insert. To overwrite, use SparseMap::insert_or_assign.

pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, (K, V)>

Insert key with value only when key is absent.

Returns Ok(&mut V) with a reference to the newly stored value on a fresh insert. Returns Err((key, value)) with the rejected pair when key is already present, so an expensive or move-only value is never silently dropped. The stored value is left unchanged on collision.

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

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

A reference to the value at key.

pub fn get_precalc<Q>(&self, key: &Q, hash: usize) -> Option<&V>

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

A reference to the value at key, using a precomputed hash.

The hash must equal hash_function().hash_key(key) or the result is unspecified.

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

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

A mutable reference to the value at key.

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

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

A reference to the key-value pair at key.

pub fn contains_key<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_key_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.

Membership reads more directly through SparseMap::contains_key. This count form mirrors the container contract where a key maps to at most one element.

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, V>

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

The range of entries equal to key.

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

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

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

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

pub fn at<Q>(&self, key: &Q) -> &V

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

A reference to the value at key, or a panic when absent.

Indexing with map[key] is the idiomatic panic-on-missing form and reads the same value. Use SparseMap::get to handle a missing key without panicking.

Panics

Panics when key is not present.

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

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

A reference to the value at key, using a precomputed hash.

Panics

Panics when key is not present.

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

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

Remove key and return its value.

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.

Use SparseMap::remove to get the removed value back. erase skips moving the value out, so it does no work beyond the tombstone.

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

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

Remove key using a precomputed hash. Returns 1 when erased, 0 otherwise.

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

Remove and return the first entry in iteration order.

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

Remove count entries starting at iteration index skip.

Entries are erased in iteration order. Erasing leaves a tombstone, which the next grow or cleanup reclaims. The walk is a single forward pass.

pub fn erase_all(&mut self)

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

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

impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>

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

pub fn entry_or_default(&mut self, key: K) -> &mut V

where V: Default,

The value at key, inserting V::default() when absent.

This is the index-access behavior of a map that default-inserts.

pub fn try_emplace<F>(&mut self, key: K, make: F) -> (&mut V, bool)

where F: FnOnce() -> V,

Insert only when key is absent, building the value on demand.

Returns a reference to the value and whether it was newly inserted. The value closure runs only when the key is absent, so a redundant call does not build or consume a value.

pub fn insert_or_assign(&mut self, key: K, value: V) -> (&mut V, bool)

Insert value at key, or overwrite the existing value.

Returns a reference to the value and whether it was newly inserted.

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

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

Keep only the entries for which keep returns true.

The key is shared and the value is mutable. Removed entries become tombstones. Each sparse array is scanned once.

impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>

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

A forward iterator over (&K, &V) pairs.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

A forward iterator over (&K, &mut V) pairs.

The key stays shared so it cannot change under the map.

pub fn keys(&self) -> Keys<'_, K, V>

A forward iterator over keys.

pub fn values(&self) -> Values<'_, K, V>

A forward iterator over shared value references.

impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>

where (K, V): Serialize,

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

Write the map through serializer in protocol order.

impl<K, V, H, E, P, S> SparseMap<K, V, H, E, P, S>

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

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

Read a map written by SparseMap::serialize.

See the engine docs for the meaning of hash_compatible.

Trait Implementations

impl<K, V, H, E, P, S> Clone for SparseMap<K, V, H, E, P, S>

where (K, V): 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, V, H, E, P, S> Debug for SparseMap<K, V, H, E, P, S>

where K: Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K, V, H, E, P, S> Default for SparseMap<K, V, H, E, P, S>

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

fn default() -> Self

An empty map with default parts and no allocation.

Available for any parameterization whose hasher, comparator, and policy are themselves Default. Places no bound on K.

impl<K, V, H, E, P, S> Eq for SparseMap<K, V, H, E, P, S>

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

impl<K, V, H, E, P, S> Extend<(K, V)> for SparseMap<K, V, H, E, P, S>

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

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

Insert every pair from iter. A key already present keeps its value.

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, V, const N: usize> From<[(K, V); N]> for SparseMap<K, V>

where K: Hash + Eq,

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

Converts to this type from the input type.

impl<K, V> FromIterator<(K, V)> for SparseMap<K, V>

where K: Hash + Eq,

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

Creates a value from an iterator.

impl<K, V, H, E, P, S, Q> Index<&Q> for SparseMap<K, V, H, E, P, S>

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

fn index(&self, key: &Q) -> &V

The value at key.

Panics

Panics when key is not present.

type Output = V

The returned type after indexing.

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

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V, H, E, P, S> IntoIterator for &'a mut SparseMap<K, V, H, E, P, S>

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, H, E, P, S> IntoIterator for SparseMap<K, V, H, E, P, S>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, H, E, P, S> PartialEq for SparseMap<K, V, H, E, P, S>

where V: PartialEq, 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.