Struct otter_nodejs_tests::SparseSecondaryMap

source · [−]
pub struct SparseSecondaryMap<K, V, S = RandomState> where
    K: Key,
    S: BuildHasher,  { /* private fields */ }
Expand description

Sparse secondary map, associate data with previously stored elements in a slot map.

A SparseSecondaryMap allows you to efficiently store additional information for each element in a slot map. You can have multiple secondary maps per slot map, but not multiple slot maps per secondary map. It is safe but unspecified behavior if you use keys from multiple different slot maps in the same SparseSecondaryMap.

A SparseSecondaryMap does not leak memory even if you never remove elements. In return, when you remove a key from the primary slot map, after any insert the space associated with the removed element may be reclaimed. Don’t expect the values associated with a removed key to stick around after an insertion has happened!

Unlike SecondaryMap, the SparseSecondaryMap is backed by a HashMap. This means its access times are higher, but it uses less memory and iterates faster if there are only a few elements of the slot map in the secondary map. If most or all of the elements in a slot map are also found in the secondary map, use a SecondaryMap instead.

The current implementation of SparseSecondaryMap requires std and is thus not available in no_std environments.

Example usage:

let mut players = SlotMap::new();
let mut health = SparseSecondaryMap::new();
let mut ammo = SparseSecondaryMap::new();

let alice = players.insert("alice");
let bob = players.insert("bob");

for p in players.keys() {
    health.insert(p, 100);
    ammo.insert(p, 30);
}

// Alice attacks Bob with all her ammo!
health[bob] -= ammo[alice] * 3;
ammo[alice] = 0;

Implementations

Constructs a new, empty SparseSecondaryMap.

Examples
let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::new();

Creates an empty SparseSecondaryMap with the given capacity of slots.

The secondary map will not reallocate until it holds at least capacity slots.

Examples
let mut sm: SlotMap<_, i32> = SlotMap::with_capacity(10);
let mut sec: SparseSecondaryMap<DefaultKey, i32> =
    SparseSecondaryMap::with_capacity(sm.capacity());

Creates an empty SparseSecondaryMap which will use the given hash builder to hash keys.

The secondary map will not reallocate until it holds at least capacity slots.

Examples
let mut sm: SlotMap<_, i32> = SlotMap::with_capacity(10);
let mut sec: SparseSecondaryMap<DefaultKey, i32, _> =
    SparseSecondaryMap::with_hasher(RandomState::new());

Creates an empty SparseSecondaryMap with the given capacity of slots, using hash_builder to hash the keys.

The secondary map will not reallocate until it holds at least capacity slots.

Examples
let mut sm: SlotMap<_, i32> = SlotMap::with_capacity(10);
let mut sec: SparseSecondaryMap<DefaultKey, i32, _> =
    SparseSecondaryMap::with_capacity_and_hasher(10, RandomState::new());

Returns the number of elements in the secondary map.

Examples
let mut sm = SlotMap::new();
let k = sm.insert(4);
let mut squared = SparseSecondaryMap::new();
assert_eq!(squared.len(), 0);
squared.insert(k, 16);
assert_eq!(squared.len(), 1);

Returns if the secondary map is empty.

Examples
let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::new();
assert!(sec.is_empty());

Returns the number of elements the SparseSecondaryMap can hold without reallocating.

Examples
let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::with_capacity(10);
assert!(sec.capacity() >= 10);

Reserves capacity for at least additional more slots in the SparseSecondaryMap. The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the new allocation size overflows usize.

Examples
let mut sec: SparseSecondaryMap<DefaultKey, i32> = SparseSecondaryMap::new();
sec.reserve(10);
assert!(sec.capacity() >= 10);

Returns true if the secondary map contains key.

Examples
let mut sm = SlotMap::new();
let k = sm.insert(4);
let mut squared = SparseSecondaryMap::new();
assert!(!squared.contains_key(k));
squared.insert(k, 16);
assert!(squared.contains_key(k));

Inserts a value into the secondary map at the given key. Can silently fail if key was removed from the originating slot map.

Returns None if this key was not present in the map, the old value otherwise.

Examples
let mut sm = SlotMap::new();
let k = sm.insert(4);
let mut squared = SparseSecondaryMap::new();
assert_eq!(squared.insert(k, 0), None);
assert_eq!(squared.insert(k, 4), Some(0));
// You don't have to use insert if the key is already in the secondary map.
squared[k] *= squared[k];
assert_eq!(squared[k], 16);

Removes a key from the secondary map, returning the value at the key if the key was not previously removed. If key was removed from the originating slot map, its corresponding entry in the secondary map may or may not already be removed.

Examples
let mut sm = SlotMap::new();
let mut squared = SparseSecondaryMap::new();
let k = sm.insert(4);
squared.insert(k, 16);
squared.remove(k);
assert!(!squared.contains_key(k));

// It's not necessary to remove keys deleted from the primary slot map, they
// get deleted automatically when their slots are reused on a subsequent insert.
squared.insert(k, 16);
sm.remove(k); // Remove k from the slot map, making an empty slot.
let new_k = sm.insert(2); // Since sm only has one empty slot, this reuses it.
assert!(!squared.contains_key(new_k)); // Space reuse does not mean equal keys.
assert!(squared.contains_key(k)); // Slot has not been reused in squared yet.
squared.insert(new_k, 4);
assert!(!squared.contains_key(k)); // Old key is no longer available.

Retains only the elements specified by the predicate.

In other words, remove all key-value pairs (k, v) such that f(k, &mut v) returns false. This method invalidates any removed keys.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();

let k1 = sm.insert(0); sec.insert(k1, 10);
let k2 = sm.insert(1); sec.insert(k2, 11);
let k3 = sm.insert(2); sec.insert(k3, 12);

sec.retain(|key, val| key == k1 || *val == 11);

assert!(sec.contains_key(k1));
assert!(sec.contains_key(k2));
assert!(!sec.contains_key(k3));

assert_eq!(2, sec.len());

Clears the secondary map. Keeps the allocated memory for reuse.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();
for i in 0..10 {
    sec.insert(sm.insert(i), i);
}
assert_eq!(sec.len(), 10);
sec.clear();
assert_eq!(sec.len(), 0);

Clears the slot map, returning all key-value pairs in arbitrary order as an iterator. Keeps the allocated memory for reuse.

When the iterator is dropped all elements in the slot map are removed, even if the iterator was not fully consumed. If the iterator is not dropped (using e.g. std::mem::forget), only the elements that were iterated over are removed.

Examples
let mut sm = SlotMap::new();
let k = sm.insert(0);
let mut sec = SparseSecondaryMap::new();
sec.insert(k, 1);
let v: Vec<_> = sec.drain().collect();
assert_eq!(sec.len(), 0);
assert_eq!(v, vec![(k, 1)]);

Returns a reference to the value corresponding to the key.

Examples
let mut sm = SlotMap::new();
let key = sm.insert("foo");
let mut sec = SparseSecondaryMap::new();
sec.insert(key, "bar");
assert_eq!(sec.get(key), Some(&"bar"));
sec.remove(key);
assert_eq!(sec.get(key), None);

Returns a mutable reference to the value corresponding to the key.

Examples
let mut sm = SlotMap::new();
let key = sm.insert("test");
let mut sec = SparseSecondaryMap::new();
sec.insert(key, 3.5);
if let Some(x) = sec.get_mut(key) {
    *x += 3.0;
}
assert_eq!(sec[key], 6.5);

An iterator visiting all key-value pairs in arbitrary order. The iterator element type is (K, &'a V).

This function must iterate over all slots, empty or not. In the face of many deleted elements it can be inefficient.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();
let k0 = sm.insert(0); sec.insert(k0, 10);
let k1 = sm.insert(1); sec.insert(k1, 11);
let k2 = sm.insert(2); sec.insert(k2, 12);

for (k, v) in sec.iter() {
    println!("key: {:?}, val: {}", k, v);
}

An iterator visiting all key-value pairs in arbitrary order, with mutable references to the values. The iterator element type is (K, &'a mut V).

This function must iterate over all slots, empty or not. In the face of many deleted elements it can be inefficient.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();
let k0 = sm.insert(1); sec.insert(k0, 10);
let k1 = sm.insert(2); sec.insert(k1, 20);
let k2 = sm.insert(3); sec.insert(k2, 30);

for (k, v) in sec.iter_mut() {
    if k != k1 {
        *v *= -1;
    }
}

assert_eq!(sec[k0], -10);
assert_eq!(sec[k1], 20);
assert_eq!(sec[k2], -30);

An iterator visiting all keys in arbitrary order. The iterator element type is K.

This function must iterate over all slots, empty or not. In the face of many deleted elements it can be inefficient.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();
let k0 = sm.insert(1); sec.insert(k0, 10);
let k1 = sm.insert(2); sec.insert(k1, 20);
let k2 = sm.insert(3); sec.insert(k2, 30);
let keys: HashSet<_> = sec.keys().collect();
let check: HashSet<_> = vec![k0, k1, k2].into_iter().collect();
assert_eq!(keys, check);

An iterator visiting all values in arbitrary order. The iterator element type is &'a V.

This function must iterate over all slots, empty or not. In the face of many deleted elements it can be inefficient.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();
let k0 = sm.insert(1); sec.insert(k0, 10);
let k1 = sm.insert(2); sec.insert(k1, 20);
let k2 = sm.insert(3); sec.insert(k2, 30);
let values: HashSet<_> = sec.values().collect();
let check: HashSet<_> = vec![&10, &20, &30].into_iter().collect();
assert_eq!(values, check);

An iterator visiting all values mutably in arbitrary order. The iterator element type is &'a mut V.

This function must iterate over all slots, empty or not. In the face of many deleted elements it can be inefficient.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();
sec.insert(sm.insert(1), 10);
sec.insert(sm.insert(2), 20);
sec.insert(sm.insert(3), 30);
sec.values_mut().for_each(|n| { *n *= 3 });
let values: HashSet<_> = sec.into_iter().map(|(_k, v)| v).collect();
let check: HashSet<_> = vec![30, 60, 90].into_iter().collect();
assert_eq!(values, check);

Gets the given key’s corresponding Entry in the map for in-place manipulation. May return None if the key was removed from the originating slot map.

Examples
let mut sm = SlotMap::new();
let mut sec = SparseSecondaryMap::new();
let k = sm.insert(1);
let v = sec.entry(k).unwrap().or_insert(10);
assert_eq!(*v, 10);

Trait Implementations

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Returns the “default value” for a type. Read more

Deserialize this value from the given Serde deserializer. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Extends a collection with the contents of an iterator. Read more

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Creates a value from an iterator. Read more

The returned type after indexing.

Performs the indexing (container[index]) operation. Read more

Performs the mutable indexing (container[index]) operation. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Convert Box<dyn Trait> (where Trait: Downcast) to Box<dyn Any>. Box<dyn Any> can then be further downcast into Box<ConcreteType> where ConcreteType implements Trait. Read more

Convert Rc<Trait> (where Trait: Downcast) to Rc<Any>. Rc<Any> can then be further downcast into Rc<ConcreteType> where ConcreteType implements Trait. Read more

Convert &Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot generate &Any’s vtable from &Trait’s. Read more

Convert &mut Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot generate &mut Any’s vtable from &mut Trait’s. Read more

Convert Arc<Trait> (where Trait: Downcast) to Arc<Any>. Arc<Any> can then be further downcast into Arc<ConcreteType> where ConcreteType implements Trait. Read more

Use this to cast from one trait object type to another. Read more

Use this to upcast a trait to one of its supertraits. Read more

Use this to cast from one trait object type to another. This method is more customizable than the dyn_cast method. Here you can also specify the “source” trait from which the cast is defined. This can for example allow using casts from a supertrait of the current trait object. Read more

Use this to cast from one trait object type to another. With this method the type parameter is a config type that uniquely specifies which cast should be preformed. Read more

Compare self to key and return true if they are equal.

Returns the argument unchanged.

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more

Instruments this type with the current Span, returning an Instrumented wrapper. Read more

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Should always be Self

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

Uses borrowed data to replace owned data, usually by cloning. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more