Struct DenseMap

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

A generic container for T keyed by densely packed integers.

DenseMap is a generic container keyed by usize that manages its own key pool. DenseMap reuses keys that are free to keep its key pool as dense as possible.

The main guarantee provided by DenseMap is that all get operations are provided in O(1) without the need to hash the keys.

All operations that mutate the DenseMap may be O(n) during resizing or compression but averages at O(1).

push will grab the lowest free id and assign it to the given value, returning the assigned id. insert can be used for assigning a specific id to an object, and returns the previous object at that id if any.

Implementations

impl<T> DenseMap<T>

pub fn new() -> Self

Creates a new empty DenseMap.

pub fn is_empty(&self) -> bool

Returns true if there are no items in DenseMap.

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

Returns a reference to the item indexed by key, or None if the key doesn’t exist.

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

Returns a mutable reference to the item indexed by key, or None if the key doesn’t exist.

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

Removes item indexed by key from the container.

Returns the removed item if it exists, or None otherwise.

Note: the worst case complexity of remove is O(key) if the backing data structure of the DenseMap is too sparse.

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

Inserts item at key.

If the DenseMap already contained an item indexed by key, insert returns it, or None otherwise.

Note: The worst case complexity of insert is O(key) if key is larger than the number of items currently held by the DenseMap.

pub fn push(&mut self, item: T) -> Key

Inserts item into the DenseMap.

push inserts a new item into the DenseMap and returns the key value allocated for item. push will allocate any key that is currently free in the internal structure, so it may return a key that was used previously but has since been removed.

Note: The worst case complexity of push is O(n) where n is the number of items held by the DenseMap. This can happen if the internal structure gets fragmented.

pub fn push_entry(&mut self, item: T) -> OccupiedEntry<'_, usize, T>

Inserts item into the DenseMap and returns an OccupiedEntry for it.

Like DenseMap::push except that it returns an entry instead of an index.

pub fn push_with( &mut self, make_item: impl FnOnce(Key) -> T, ) -> OccupiedEntry<'_, usize, T>

Creates an item in the DenseMap via functor.

Like DenseMap::push except that the item is constructed by the provided function, which is passed its index.

pub fn insertion_ordered_iter(&self) -> InsertionOrderedIter<'_, T>

Creates an iterator over the containing items and their associated keys.

The iterator will return items in insertion order.

pub fn key_ordered_iter(&self) -> KeyOrderedIter<'_, T>

Creates an iterator over the containing items and their associated keys.

The iterator will return items in key order.

pub fn key_ordered_iter_mut(&mut self) -> KeyOrderedIterMut<'_, T>

Creates a mutable iterator over the containing items and their associated keys.

The iterator will return items in key order.

pub fn key_ordered_into_iter(self) -> IntoKeyOrderedIter<T>

Consumes the DenseMap and returns an iterator over the contained items and their associated keys.

The iterator will return items in key order.

pub fn entry(&mut self, key: usize) -> Entry<'_, usize, T>

Gets the given key’s corresponding entry in the map for in-place manipulation.

pub fn key_ordered_retain<F: FnMut(&T) -> bool>(&mut self, should_retain: F)

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&e) returns false. The elements are visited in ascending key order.

Trait Implementations

impl<T: Debug> Debug for DenseMap<T>

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

Formats the value using the given formatter.

impl<T> Default for DenseMap<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T> IntoIterator for &'a DenseMap<T>

type Item = (usize, &'a T)

The type of the elements being iterated over.

type IntoIter = KeyOrderedIter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut DenseMap<T>

type Item = (usize, &'a mut T)

The type of the elements being iterated over.

type IntoIter = KeyOrderedIterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for DenseMap<T>

type Item = (usize, T)

The type of the elements being iterated over.

type IntoIter = IntoKeyOrderedIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.