pub struct Tec<IndexT, DataT> { /* private fields */ }
Expand description
Short for tombstone-based vector. Inspired by generational-arena, but without the generation stuff.
Features
- index stability when deleting an element
- maintain freed list, and is basically free for large structs
Use case: you have compact data that needs to be inserted & deleted while other objects maintain their index-based references.
Don’t use it if:
- the data are sparse (use a HashMap or
Entities
instead) - you don’t need to remove data (use a Vec with
Sequence
instead)
use stable_id::Tec;
// use the `derive_more` crate to shortern the list
#[derive(derive_stable_id::StableId, Debug)]
struct Id(u8);
struct Data { field: usize }
let mut storage: Tec<Id, Data> = Default::default();
assert_eq!(storage.alloc(Data {field: 123}), Id(0));
assert_eq!(storage.get(Id(0)).unwrap().field, 123);
Implementations§
source§impl<IndexT, DataT> Tec<IndexT, DataT>where
IndexT: CastUsize + Ord + Copy + Maximum,
impl<IndexT, DataT> Tec<IndexT, DataT>where IndexT: CastUsize + Ord + Copy + Maximum,
pub fn with_capacity(capacity: usize) -> Self
pub fn is_empty(&self) -> bool
pub fn clear(&mut self)
sourcepub fn alloc(&mut self, data: DataT) -> IndexT
pub fn alloc(&mut self, data: DataT) -> IndexT
Allocates an id from the given data
.
Note: can store at most IndexT::max_value() - 1 elements, because
the next free node needs to be count + 1.
pub fn get(&self, index: IndexT) -> Option<&DataT>
pub fn get_mut(&mut self, index: IndexT) -> Option<&mut DataT>
pub fn iter(&self) -> impl Iterator<Item = &DataT> + DoubleEndedIterator
pub fn iter_with_id( &self ) -> impl Iterator<Item = (IndexT, &DataT)> + DoubleEndedIterator
pub fn iter_mut( &mut self ) -> impl Iterator<Item = &mut DataT> + DoubleEndedIterator
pub fn iter_mut_with_id( &mut self ) -> impl Iterator<Item = (IndexT, &mut DataT)> + DoubleEndedIterator
pub fn into_iter_with_id( self ) -> impl Iterator<Item = (IndexT, DataT)> + DoubleEndedIterator
sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
The amount of occupied space in the underlying vec
.
Note:
self.len() <= self.capacity() == self.vec.len() <= self.vec.capacity()
sourcepub fn coalesce<F>(&mut self, f: F)where
F: FnMut(IndexT, IndexT),
pub fn coalesce<F>(&mut self, f: F)where F: FnMut(IndexT, IndexT),
Coalesce the data by removing the dead slots. Takes a function f(old_id, new_id)
that allows you to deal with changes made by the process, i.e. say in your game model,
you have an entity which occupied old_id
, you would need to change all references
to use the new_id
.
This is intended to be used before saving a game.
Note: this algorithm is O(n lg n) due to the use of binary heap.