Struct SparseMap

Source

pub struct SparseMap<T> { /* private fields */ }

Expand description

A sparse, generational map keyed by Key.

SparseMap provides stable keys with generation to prevent use-after-free bugs. Internally, it reuses vacant slots while incrementing a generation counter to invalidate stale keys.

§Guarantees

Insertion is O(1).
Removal is O(1).
Lookup is O(1).
Keys are invalidated once their value is removed.

Implementations§

Source §

impl<T> SparseMap<T>

Source

pub fn new() -> Self

Creates a new empty sparse map.

Source

pub fn insert(&mut self, value: T) -> Key

Inserts a value into the map and returns a unique Key.

Vacant slots are reused when possible. If a slot is reused, its generation counter is incremented to invalidate old keys.

Source

pub fn remove(&mut self, key: &Key) -> Option<T>

Removes a value associated with the given key.

Returns None if the key is invalid or already removed. The slot is marked for reuse.

Source

pub fn get(&self, key: &Key) -> Option<&T>

Returns an immutable reference to the value for the given key if present.

Source

pub fn get_mut(&mut self, key: &Key) -> Option<&mut T>

Returns a mutable reference to the value for the given key if present.

Source

pub fn scope<F, R>(&mut self, key: &Key, f: F) -> Option<R>
where F: FnOnce(&mut Self, &mut T) -> R,

Temporarily takes ownership of the value associated with key, passes it to f, and then places it back into the map.

This enables safe, scoped mutation of a value while still allowing f to mutate the map itself (e.g. insert or remove other entries) without violating Rust’s aliasing rules.

Returns None if key does not currently refer to a live value.

§Guarantees

The value is removed from the map for the duration of f.
The value is restored to the same slot after f returns.
The key remains valid if and only if it was valid before the call.

§Example

use sparse_map::SparseMap;

let mut map = SparseMap::new();
let key = map.insert(42);

map.scope(&key, |map, value| {
    *value += 2;
    map.insert(24);
});

assert_eq!(map.get(&key), Some(&44));