Struct vec_arena::Arena

pub struct Arena<T> { /* fields omitted */ }

An object arena.

Arena<T> holds an array of slots for storing objects. Every slot is always in one of two states: occupied or vacant.

Essentially, this is equivalent to Vec<Option<T>>.

Insert and remove

When inserting a new object into arena, a vacant slot is found and then the object is placed into the slot. If there are no vacant slots, the array is reallocated with bigger capacity. The cost of insertion is amortized O(1).

When removing an object, the slot containing it is marked as vacant and the object is returned. The cost of removal is O(1).

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert(10);
let b = arena.insert(20);

assert_eq!(a, 0); // 10 was placed at index 0
assert_eq!(b, 1); // 20 was placed at index 1

assert_eq!(arena.remove(a), Some(10));
assert_eq!(arena.get(a), None); // slot at index 0 is now vacant

assert_eq!(arena.insert(30), 0); // slot at index 0 is reused

Indexing

You can also access objects in an arena by index, just like you would in a Vec. However, accessing a vacant slot by index or using an out-of-bounds index will result in panic.

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert(10);
let b = arena.insert(20);

assert_eq!(arena[a], 10);
assert_eq!(arena[b], 20);

arena[a] += arena[b];
assert_eq!(arena[a], 30);

To access slots without fear of panicking, use get() and get_mut(), which return Options.

Implementations

impl<T> Arena<T>

pub fn new() -> Self

Constructs a new, empty arena.

The arena will not allocate until objects are inserted into it.

Examples

use vec_arena::Arena;

let mut arena: Arena<i32> = Arena::new();

pub fn with_capacity(cap: usize) -> Self

Constructs a new, empty arena with the specified capacity (number of slots).

The arena will be able to hold exactly cap objects without reallocating. If cap is 0, the arena will not allocate.

Examples

use vec_arena::Arena;

let mut arena = Arena::with_capacity(10);

assert_eq!(arena.len(), 0);
assert_eq!(arena.capacity(), 10);

// These inserts are done without reallocating...
for i in 0..10 {
    arena.insert(i);
}
assert_eq!(arena.capacity(), 10);

// ... but this one will reallocate.
arena.insert(11);
assert!(arena.capacity() > 10);

pub fn capacity(&self) -> usize

Returns the number of slots in the arena.

Examples

use vec_arena::Arena;

let arena: Arena<i32> = Arena::with_capacity(10);
assert_eq!(arena.capacity(), 10);

pub fn len(&self) -> usize

Returns the number of occupied slots in the arena.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
assert_eq!(arena.len(), 0);

for i in 0..10 {
    arena.insert(());
    assert_eq!(arena.len(), i + 1);
}

pub fn is_empty(&self) -> bool

Returns true if all slots are vacant.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
assert!(arena.is_empty());

arena.insert(1);
assert!(!arena.is_empty());

pub fn next_vacant(&self) -> usize

Returns the index of the slot that next insert will use if no mutating calls take place in between.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();

let a = arena.next_vacant();
let b = arena.insert(1);
assert_eq!(a, b);
let c = arena.next_vacant();
let d = arena.insert(2);
assert_eq!(c, d);

pub fn insert(&mut self, object: T) -> usize

Inserts an object into the arena and returns the slot index it was stored in.

The arena will reallocate if it’s full.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();

let a = arena.insert(1);
let b = arena.insert(2);
assert!(a != b);

pub fn remove(&mut self, index: usize) -> Option<T>

Removes the object stored at index from the arena and returns it.

If the slot is vacant or index is out of bounds, None will be returned.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert("hello");

assert_eq!(arena.len(), 1);
assert_eq!(arena.remove(a), Some("hello"));

assert_eq!(arena.len(), 0);
assert_eq!(arena.remove(a), None);

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

Retains objects for which the closure returns true.

All other objects will be removed from the arena.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();

let a = arena.insert(0);
let b = arena.insert(1);
let c = arena.insert(2);

arena.retain(|k, v| k == a || *v == 1);

assert!(arena.get(a).is_some());
assert!(arena.get(b).is_some());
assert!(arena.get(c).is_none());

pub fn clear(&mut self)

Clears the arena, removing and dropping all objects it holds.

Keeps the allocated memory for reuse.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
for i in 0..10 {
    arena.insert(i);
}

assert_eq!(arena.len(), 10);
arena.clear();
assert_eq!(arena.len(), 0);

pub fn get(&self, index: usize) -> Option<&T>

Returns a reference to the object stored at index.

If the slot is vacant or index is out of bounds, None will be returned.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let index = arena.insert("hello");

assert_eq!(arena.get(index), Some(&"hello"));
arena.remove(index);
assert_eq!(arena.get(index), None);

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the object stored at index.

If the slot is vacant or index is out of bounds, None will be returned.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let index = arena.insert(7);

assert_eq!(arena.get_mut(index), Some(&mut 7));
*arena.get_mut(index).unwrap() *= 10;
assert_eq!(arena.get_mut(index), Some(&mut 70));

pub fn swap(&mut self, a: usize, b: usize)

Swaps two objects in the arena.

The two indices are a and b.

Panics

Panics if any of the indices is out of bounds or any of the slots is vacant.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
let a = arena.insert(7);
let b = arena.insert(8);

arena.swap(a, b);
assert_eq!(arena.get(a), Some(&8));
assert_eq!(arena.get(b), Some(&7));

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more objects to be inserted.

The arena may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert("hello");

arena.reserve(10);
assert!(arena.capacity() >= 11);

pub fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more objects to be inserted.

Note that the allocator may give the arena more space than it requests.

Panics

Panics if the new capacity overflows usize.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert("hello");

arena.reserve_exact(10);
assert!(arena.capacity() >= 11);

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

Returns an iterator over occupied slots.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert(1);
arena.insert(2);
arena.insert(4);

let mut iterator = arena.iter();
assert_eq!(iterator.next(), Some((0, &1)));
assert_eq!(iterator.next(), Some((1, &2)));
assert_eq!(iterator.next(), Some((2, &4)));

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Returns an iterator that returns mutable references to objects.

Examples

use vec_arena::Arena;

let mut arena = Arena::new();
arena.insert("zero".to_string());
arena.insert("one".to_string());
arena.insert("two".to_string());

for (index, object) in arena.iter_mut() {
    *object = index.to_string() + " " + object;
}

let mut iterator = arena.iter();
assert_eq!(iterator.next(), Some((0, &"0 zero".to_string())));
assert_eq!(iterator.next(), Some((1, &"1 one".to_string())));
assert_eq!(iterator.next(), Some((2, &"2 two".to_string())));

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the arena as much as possible.

It will drop down as close as possible to the length but the allocator may still inform the arena that there is space for a few more elements.

Examples

use vec_arena::Arena;

let mut arena = Arena::with_capacity(10);
arena.insert("first".to_string());
arena.insert("second".to_string());
arena.insert("third".to_string());
assert_eq!(arena.capacity(), 10);
arena.shrink_to_fit();
assert!(arena.capacity() >= 3);

Trait Implementations

impl<T: Clone> Clone for Arena<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for Arena<T>

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

Formats the value using the given formatter.

impl<T> Default for Arena<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> FromIterator<T> for Arena<T>

fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Arena<T>

Creates a value from an iterator.

impl<T> Index<usize> for Arena<T>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &T

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for Arena<T>

fn index_mut(&mut self, index: usize) -> &mut T

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

impl<T> IntoIterator for Arena<T>

type Item = (usize, T)

The type of the elements being iterated over.

type IntoIter = IntoIter<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 Arena<T>

type Item = (usize, &'a T)

The type of the elements being iterated over.

type IntoIter = Iter<'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 Arena<T>

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

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.