Struct slotmap::SecondaryMap

source ·
pub struct SecondaryMap<K: Key, V> { /* private fields */ }
Expand description

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

A SecondaryMap 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 SecondaryMap.

A SecondaryMap 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!

Finally a note on memory complexity, the SecondaryMap can use memory for each slot in the primary slot map, and has to iterate over every slot during iteration, regardless of whether you have inserted an associative value at that key or not. If you have some property that you only expect to set for a minority of keys, use a SparseSecondaryMap, which is backed by a HashMap.

Example usage:

let mut players = SlotMap::new();
let mut health = SecondaryMap::new();
let mut ammo = SecondaryMap::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§

source§

impl<K: Key, V> SecondaryMap<K, V>

source

pub fn new() -> Self

Constructs a new, empty SecondaryMap.

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

pub fn with_capacity(capacity: usize) -> Self

Creates an empty SecondaryMap with the given capacity of slots.

The secondary map will not reallocate until it holds at least capacity slots. Even inserting a single key-value pair might require as many slots as the slot map the key comes from, so it’s recommended to match the capacity of a secondary map to its corresponding slot map.

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

pub fn len(&self) -> usize

Returns the number of elements in the secondary map.

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

pub fn is_empty(&self) -> bool

Returns if the secondary map is empty.

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

pub fn capacity(&self) -> usize

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

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

pub fn set_capacity(&mut self, new_capacity: usize)

Sets the capacity of the SecondaryMap to new_capacity, if it is bigger than the current capacity.

It is recommended to set the capacity of a SecondaryMap to the capacity of its corresponding slot map before inserting many new elements to prevent frequent reallocations. The collection may reserve more space than requested.

Panics

Panics if the new allocation size overflows usize.

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

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

Returns true if the secondary map contains key.

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

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

Inserts a value into the secondary map at the given key. Can silently fail and return None 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 = SecondaryMap::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);
source

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

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 = SecondaryMap::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.
source

pub fn retain<F>(&mut self, f: F)
where F: FnMut(K, &mut V) -> bool,

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.

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 = SecondaryMap::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!(sec.len(), 2);
source

pub fn clear(&mut self)

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

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 = SecondaryMap::new();
for i in 0..10 {
    sec.insert(sm.insert(i), i);
}
assert_eq!(sec.len(), 10);
sec.clear();
assert_eq!(sec.len(), 0);
source

pub fn drain(&mut self) -> Drain<'_, K, V>

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.

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 k = sm.insert(0);
let mut sec = SecondaryMap::new();
sec.insert(k, 1);
let v: Vec<_> = sec.drain().collect();
assert_eq!(sec.len(), 0);
assert_eq!(v, vec![(k, 1)]);
source

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

Returns a reference to the value corresponding to the key.

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

pub unsafe fn get_unchecked(&self, key: K) -> &V

Returns a reference to the value corresponding to the key without version or bounds checking.

Safety

This should only be used if contains_key(key) is true. Otherwise it is potentially unsafe.

Examples
let mut sm = SlotMap::new();
let key = sm.insert("foo");
let mut sec = SecondaryMap::new();
sec.insert(key, "bar");
assert_eq!(unsafe { sec.get_unchecked(key) }, &"bar");
sec.remove(key);
// sec.get_unchecked(key) is now dangerous!
source

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

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 = SecondaryMap::new();
sec.insert(key, 3.5);
if let Some(x) = sec.get_mut(key) {
    *x += 3.0;
}
assert_eq!(sec[key], 6.5);
source

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

Returns a mutable reference to the value corresponding to the key without version or bounds checking.

Safety

This should only be used if contains_key(key) is true. Otherwise it is potentially unsafe.

Examples
let mut sm = SlotMap::new();
let key = sm.insert("foo");
let mut sec = SecondaryMap::new();
sec.insert(key, "bar");
unsafe { *sec.get_unchecked_mut(key) = "baz" };
assert_eq!(sec[key], "baz");
sec.remove(key);
// sec.get_unchecked_mut(key) is now dangerous!
source

pub fn get_disjoint_mut<const N: usize>( &mut self, keys: [K; N] ) -> Option<[&mut V; N]>

Returns mutable references to the values corresponding to the given keys. All keys must be valid and disjoint, otherwise None is returned.

Requires at least stable Rust version 1.51.

Examples
let mut sm = SlotMap::new();
let mut sec = SecondaryMap::new();
let ka = sm.insert(()); sec.insert(ka, "butter");
let kb = sm.insert(()); sec.insert(kb, "apples");
let kc = sm.insert(()); sec.insert(kc, "charlie");
sec.remove(kc); // Make key c invalid.
assert_eq!(sec.get_disjoint_mut([ka, kb, kc]), None); // Has invalid key.
assert_eq!(sec.get_disjoint_mut([ka, ka]), None); // Not disjoint.
let [a, b] = sec.get_disjoint_mut([ka, kb]).unwrap();
std::mem::swap(a, b);
assert_eq!(sec[ka], "apples");
assert_eq!(sec[kb], "butter");
source

pub unsafe fn get_disjoint_unchecked_mut<const N: usize>( &mut self, keys: [K; N] ) -> [&mut V; N]

Returns mutable references to the values corresponding to the given keys. All keys must be valid and disjoint.

Requires at least stable Rust version 1.51.

Safety

This should only be used if contains_key(key) is true for every given key and no two keys are equal. Otherwise it is potentially unsafe.

Examples
let mut sm = SlotMap::new();
let mut sec = SecondaryMap::new();
let ka = sm.insert(()); sec.insert(ka, "butter");
let kb = sm.insert(()); sec.insert(kb, "apples");
let [a, b] = unsafe { sec.get_disjoint_unchecked_mut([ka, kb]) };
std::mem::swap(a, b);
assert_eq!(sec[ka], "apples");
assert_eq!(sec[kb], "butter");
source

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

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 = SecondaryMap::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 sm.iter() {
    println!("key: {:?}, val: {}", k, v);
}
source

pub fn iter_mut(&mut self) -> IterMut<'_, 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 = SecondaryMap::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);
source

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

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 = SecondaryMap::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);
source

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

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 = SecondaryMap::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);
source

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

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 = SecondaryMap::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);
source

pub fn entry(&mut self, key: K) -> Option<Entry<'_, K, V>>

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 = SecondaryMap::new();
let k = sm.insert(1);
let v = sec.entry(k).unwrap().or_insert(10);
assert_eq!(*v, 10);

Trait Implementations§

source§

impl<K: Clone + Key, V: Clone> Clone for SecondaryMap<K, V>

source§

fn clone(&self) -> SecondaryMap<K, V>

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<K: Debug + Key, V: Debug> Debug for SecondaryMap<K, V>

source§

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

Formats the value using the given formatter. Read more
source§

impl<K: Key, V> Default for SecondaryMap<K, V>

source§

fn default() -> Self

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

impl<'a, K: Key, V: 'a + Copy> Extend<(K, &'a V)> for SecondaryMap<K, V>

source§

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

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

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

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. Read more
source§

impl<K: Key, V> Extend<(K, V)> for SecondaryMap<K, V>

source§

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

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

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

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. Read more
source§

impl<K: Key, V> FromIterator<(K, V)> for SecondaryMap<K, V>

source§

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

Creates a value from an iterator. Read more
source§

impl<K: Key, V> Index<K> for SecondaryMap<K, V>

§

type Output = V

The returned type after indexing.
source§

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

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

impl<K: Key, V> IndexMut<K> for SecondaryMap<K, V>

source§

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

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

impl<'a, K: Key, V> IntoIterator for &'a SecondaryMap<K, V>

§

type Item = (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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

impl<'a, K: Key, V> IntoIterator for &'a mut SecondaryMap<K, V>

§

type Item = (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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

impl<K: Key, V> IntoIterator for SecondaryMap<K, V>

§

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?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
source§

impl<K: Key, V: PartialEq> PartialEq for SecondaryMap<K, V>

source§

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl<K: Key, V: Eq> Eq for SecondaryMap<K, V>

Auto Trait Implementations§

§

impl<K, V> RefUnwindSafe for SecondaryMap<K, V>
where V: RefUnwindSafe,

§

impl<K, V> Send for SecondaryMap<K, V>
where V: Send,

§

impl<K, V> Sync for SecondaryMap<K, V>
where V: Sync,

§

impl<K, V> Unpin for SecondaryMap<K, V>
where V: Unpin,

§

impl<K, V> UnwindSafe for SecondaryMap<K, V>
where V: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

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

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

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

fn clone_into(&self, target: &mut T)

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

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.