Struct stable_vec::StableVec

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

A Vec<T>-like collection which guarantees stable indices and features O(1) deletion of elements.

Why?

The standard Vec<T> always stores all elements contiguous. While this has many advantages (most notable: cache friendliness), it has the disadvantage that you can't simply remove an element from the middle; at least not without shifting all elements after it to the left. And this has two major drawbacks:

1. It has a linear O(n) time complexity
2. It invalidates all indices of the shifted elements

Invalidating an index means that a given index i who referred to an element a before, now refers to another element b. On the contrary, a stable index means, that the index always refers to the same element.

Stable indices are needed in quite a few situations. One example are graph data structures (or complex data structures in general). Instead of allocating heap memory for every node and edge, all nodes are stored in a vector and all edges are stored in a vector. But how does the programmer unambiguously refer to one specific node? A pointer is not possible due to the reallocation strategy of most dynamically growing arrays (the pointer itself is not stable). Thus, often the index is used.

But in order to use the index, it has to be stable. This is one example, where this data structure comes into play.

How?

Actually, the implementation of this stable vector is very simple. We can trade O(1) deletions and stable indices for a higher memory consumption.

When StableVec::remove() is called, the element is just marked as "deleted", but no element is actually touched. This has the very obvious disadvantage that deleted objects just stay in memory and waste space. This is also the most important thing to understand:

The memory requirement of this data structure is O(|inserted elements|); instead of O(|inserted elements| - |removed elements|). The latter is the memory requirement of normal Vec<T>. Thus, if deletions are far more numerous than insertions in your situation, then this data structure is probably not fitting your needs.

Why not?

As mentioned above, this data structure is very simple and has many disadvantages on its own. Here are some reason not to use it:

• You don't need stable indices or O(1) removal
• Your deletions significantly outnumber your insertions
• You want to choose your keys/indices
• Lookup times do not matter so much to you

Especially in the last two cases, you could consider using a HashMap with integer keys, best paired with a fast hash function for small keys.

If you not only want stable indices, but stable pointers, you might want to use something similar to a linked list. Although: think carefully about your problem before using a linked list.

Note

This type's interface is very similar to the Vec<T> interface from the Rust standard library. When in doubt about what a method is doing, please consult the official Vec<T> documentation first.

Method overview

(there are more methods than mentioned in this overview)

Associated functions

• new()
• with_capacity()

Adding and removing elements

• push()
• pop()
• remove()

Accessing elements

• get() (returns Option<&T>)
• the [] index operator (returns &T)
• get_mut() (returns Option<&mut T>)
• the mutable [] index operator (returns &mut T)
• remove() (returns Option<T>)

Stable vector specific

• has_element_at()
• next_index()
• is_compact()
• make_compact()
• reordering_make_compact()

Number of elements

• is_empty()
• num_elements()

Capacity management

• capacity()
• shrink_to_fit()
• reserve()

Methods

impl<T> StableVec<T>

pub fn new() -> Self

Constructs a new, empty StableVec<T>.

The stable-vector will not allocate until elements are pushed onto it.

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty StableVec<T> with the specified capacity.

The stable-vector will be able to hold exactly capacity elements without reallocating. If capacity is 0, the stable-vector will not allocate any memory.

pub fn from_vec(vec: Vec<T>) -> Self

Creates a StableVec<T> from the given Vec<T>. The elements are not copied and the indices of the vector are preserved.

Note that this function will still allocate memory to store meta data.

Example

let mut sv = StableVec::from_vec(vec!['★', '♥']);

assert_eq!(sv.get(0), Some(&'★'));
assert_eq!(sv.get(1), Some(&'♥'));
assert_eq!(sv.num_elements(), 2);
assert!(sv.is_compact());

sv.remove(0);
assert_eq!(sv.get(1), Some(&'♥'));

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

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

pub fn push(&mut self, elem: T) -> usize

Appends a new element to the back of the collection and returns the index of the inserted element.

The inserted element will always be accessable via the returned index.

Example

let mut sv = StableVec::new();
let star_idx = sv.push('★');
let heart_idx = sv.push('♥');

assert_eq!(sv.get(heart_idx), Some(&'♥'));

// After removing the star we can still use the heart's index to access
// the element!
sv.remove(star_idx);
assert_eq!(sv.get(heart_idx), Some(&'♥'));

pub fn pop(&mut self) -> Option<T>

Removes and returns the last element from this collection, or None if it's empty.

This method uses exactly the same deletion strategy as remove().

Note

This method needs to find index of the last valid element. Finding it has a worst case time complexity of O(n). If you already know the index, use remove() instead.

pub fn insert_into_hole(&mut self, index: usize, elem: T) -> Result<(), T>

Inserts the given value at the given index if there is a hole there.

If there is an element marked as "deleted" at index, the elem is inserted at that position and Ok(()) is returned. If index is out of bounds or there is an existing element at that position, the vector is not changed and elem is returned as Err(elem).

Example

let mut sv = StableVec::new();
let star_idx = sv.push('★');
let heart_idx = sv.push('♥');

// Inserting fails: there isn't a hole yet.
assert_eq!(sv.insert_into_hole(star_idx, 'x'), Err('x'));
assert_eq!(sv.num_elements(), 2);

// After removing the star...
sv.remove(star_idx);
assert_eq!(sv.num_elements(), 1);

// ...we can insert a new element at its place.
assert_eq!(sv.insert_into_hole(star_idx, 'x'), Ok(()));
assert_eq!(sv[star_idx], 'x');
assert_eq!(sv.num_elements(), 2);

pub fn grow(&mut self, count: usize)

Grows the size of the stable vector by inserting deleted elements.

This method does not add existing elements, but merely "deleted" ones. Using this only makes sense when you are intending to use the holes with insert_into_hole() later. Otherwise, this method will just waste memory.

Example

let mut sv = StableVec::new();
let star_idx = sv.push('★');

// After we inserted one element, the next element sits at index 1, as
// expected.
assert_eq!(sv.next_index(), 1);

sv.grow(2); // insert two deleted elements

assert_eq!(sv.num_elements(), 1); // Still only one existing element
assert_eq!(sv.next_index(), 3); // Due to grow(2), we skip two indices

// Now we can insert an element at index 2.
sv.insert_into_hole(2, 'x').unwrap();
assert_eq!(sv.num_elements(), 2);

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

Removes and returns the element at position index if there exists an element at that index (as defined by has_element_at()).

Removing an element only marks it as "deleted" without touching the actual data. In particular, the elements after the given index are not shifted to the left. Thus, the time complexity of this method is O(1).

Example

let mut sv = StableVec::new();
let star_idx = sv.push('★');
let heart_idx = sv.push('♥');

assert_eq!(sv.remove(star_idx), Some('★'));
assert_eq!(sv.remove(star_idx), None); // the star was already removed

// We can use the heart's index here. It has not been invalidated by
// the removal of the star.
assert_eq!(sv.remove(heart_idx), Some('♥'));
assert_eq!(sv.remove(heart_idx), None); // the heart was already removed

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

Returns a reference to the element at the given index, or None if there exists no element at that index.

If you are calling unwrap() on the result of this method anyway, rather use the index operator instead: stable_vec[index].

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

Returns a mutable reference to the element at the given index, or None if there exists no element at that index.

If you are calling unwrap() on the result of this method anyway, rather use the index operator instead: stable_vec[index].

pub fn has_element_at(&self, index: usize) -> bool

Returns true if there exists an element at the given index, false otherwise.

An element is said to exist if the index is not out of bounds and the element at the given index was not removed yet.

Example

let mut sv = StableVec::new();
assert!(!sv.has_element_at(3));         // no: index out of bounds

let heart_idx = sv.push('♥');
assert!(sv.has_element_at(heart_idx));  // yes

sv.remove(heart_idx);
assert!(!sv.has_element_at(heart_idx)); // no: was removed

pub fn shrink_to_fit(&mut self)

Calls shrink_to_fit() on the underlying Vec<T>.

Note that this does not move existing elements around and thus does not invalidate indices. It only calls shrink_to_fit() on the Vec<T> that holds the actual data.

If you want to compact this StableVec by removing deleted elements, use the method make_compact() instead.

pub fn make_compact(&mut self)

Rearranges elements to reclaim memory. Invalidates indices!

After calling this method, all existing elements stored contiguously in memory. You might want to call shrink_to_fit() afterwards to actually free memory previously used by removed elements. This method itself does not deallocate any memory.

In comparison to reordering_make_compact(), this method does not change the order of elements. Due to this, this method is a bit slower.

Warning

This method invalidates the indices of all elements that are stored after the first hole in the stable vector!

pub fn reordering_make_compact(&mut self)

Rearranges elements to reclaim memory. Invalidates indices and changes the order of the elements!

After calling this method, all existing elements stored contiguously in memory. You might want to call shrink_to_fit() afterwards to actually free memory previously used by removed elements. This method itself does not deallocate any memory.

If you do need to preserve the order of elements, use make_compact() instead. However, if you don't care about element order, you should prefer using this method, because it is faster.

Warning

This method invalidates the indices of all elements that are stored after the first hole and it does not preserve the order of elements!

pub fn is_compact(&self) -> bool

Returns true if all existing elements are stored contiguously from the beginning.

This method returning true means that no memory is wasted for removed elements.

Example

let mut sv = StableVec::from(&[0, 1, 2, 3, 4]);
assert!(sv.is_compact());

sv.remove(1);
assert!(!sv.is_compact());

pub fn num_elements(&self) -> usize

Returns the number of existing elements in this collection.

As long as remove() is never called, num_elements() equals next_index(). Once it is called, num_elements() will always be less than next_index() (assuming make_compact() is not called).

Example

let mut sv = StableVec::new();
assert_eq!(sv.num_elements(), 0);

let heart_idx = sv.push('♥');
assert_eq!(sv.num_elements(), 1);

sv.remove(heart_idx);
assert_eq!(sv.num_elements(), 0);

pub fn is_empty(&self) -> bool

Returns true if this collection doesn't contain any existing elements.

This means that is_empty() returns true iff no elements were inserted or all inserted elements were removed again.

Example

let mut sv = StableVec::new();
assert!(sv.is_empty());

let heart_idx = sv.push('♥');
assert!(!sv.is_empty());

sv.remove(heart_idx);
assert!(sv.is_empty());

pub fn clear(&mut self)

Removes all elements from this collection.

After calling this, num_elements() will return 0. All indices are invalidated. However, no memory is deallocated, so the capacity stays as it was before.

Example

let mut sv = StableVec::from(&['a', 'b']);

sv.clear();
assert_eq!(sv.num_elements(), 0);
assert!(sv.capacity() >= 2);

pub fn capacity(&self) -> usize

Returns the number of elements the stable-vector can hold without reallocating.

pub fn next_index(&self) -> usize

Returns the index that would be returned by calling push().

Example

let mut sv = StableVec::from(&['a', 'b', 'c']);

let next_index = sv.next_index();
let index_of_d = sv.push('d');

assert_eq!(next_index, index_of_d);

Important traits for Iter<'a, T>

impl<'a, T: 'a> Iterator for Iter<'a, T> type Item = &'a T;

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

Returns an iterator over immutable references to the existing elements of this stable vector.

Note that you can also use the IntoIterator implementation of &StableVec to obtain the same iterator.

Example

let mut sv = StableVec::from(&[0, 1, 2, 3, 4]);
sv.remove(1);

// Using the `iter()` method to apply a `filter()`.
let mut it = sv.iter().filter(|&&n| n <= 3);
assert_eq!(it.next(), Some(&0));
assert_eq!(it.next(), Some(&2));
assert_eq!(it.next(), Some(&3));
assert_eq!(it.next(), None);

// Simple iterate using the implicit `IntoIterator` conversion of the
// for-loop:
for e in &sv {
    println!("{:?}", e);
}

Important traits for IterMut<'a, T>

impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut T;

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

Returns an iterator over mutable references to the existing elements of this stable vector.

Note that you can also use the IntoIterator implementation of &mut StableVec to obtain the same iterator.

Through this iterator, the elements within the stable vector can be mutated.

Examples

let mut sv = StableVec::from(&[1.0, 2.0, 3.0]);

for e in &mut sv {
    *e *= 2.0;
}

assert_eq!(sv, &[2.0, 4.0, 6.0] as &[_]);

Important traits for Keys<'a>

impl<'a> Iterator for Keys<'a> type Item = usize;

pub fn keys(&self) -> Keys

Returns an iterator over all valid indices of this stable vector.

Example

let mut sv = StableVec::from(&['a', 'b', 'c', 'd']);
sv.remove(1);

let mut it = sv.keys();
assert_eq!(it.next(), Some(0));
assert_eq!(it.next(), Some(2));
assert_eq!(it.next(), Some(3));
assert_eq!(it.next(), None);

Simply using the for-loop:

let mut sv = StableVec::from(&['a', 'b', 'c', 'd']);

for index in sv.keys() {
    println!("index: {}", index);
}

pub fn contains<U>(&self, item: &U) -> bool where     U: PartialEq<T>,

Returns true if the stable vector contains an element with the given value, false otherwise.

let mut sv = StableVec::from(&['a', 'b', 'c']);
assert!(sv.contains(&'b'));

sv.remove(1);   // 'b' is stored at index 1
assert!(!sv.contains(&'b'));

pub fn into_vec(self) -> Vec<T>

Returns the stable vector as a standard Vec<T>.

Returns a vector which contains all existing elements from this stable vector. All indices might be invalidated! This method might call make_compact(); see that method's documentation to learn about the effects on indices.

This method does not allocate memory.

Note

If the stable vector is not compact (as defined by is_compact()), the runtime complexity of this function is O(n), because make_compact() needs to be called.

Example

let mut sv = StableVec::from(&['a', 'b', 'c']);
sv.remove(1);   // 'b' lives at index 1

assert_eq!(sv.into_vec(), vec!['a', 'c']);

pub fn retain<P>(&mut self, should_be_kept: P) where     P: FnMut(&T) -> bool,

Retains only the elements specified by the given predicate.

Each element e for which should_be_kept(&e) returns false is removed from the stable vector.

Example

let mut sv = StableVec::from(&[1, 2, 3, 4, 5]);
sv.retain(|&e| e % 2 == 0);

assert_eq!(sv, &[2, 4] as &[_]);

pub fn extend_from_slice(&mut self, new_elements: &[T]) where     T: Clone,

Appends all elements in new_elements to this StableVec<T>. This is equivalent to calling push() for each element.

Trait Implementations

impl<T, S> From<S> for StableVec<T> where     S: AsRef<[T]>,     T: Clone,

fn from(slice: S) -> Self

Performs the conversion.

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

type Item = &'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 StableVec<T>

type Item = &'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.

impl<T: Eq> Eq for StableVec<T>

impl<T> Drop for StableVec<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> Extend<T> for StableVec<T>

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

Extends a collection with the contents of an iterator.

impl<T> Default for StableVec<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T: PartialEq> PartialEq<StableVec<T>> for StableVec<T>

fn eq(&self, other: &StableVec<T>) -> bool

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

fn ne(&self, other: &StableVec<T>) -> bool

This method tests for !=.

impl<A, B> PartialEq<[B]> for StableVec<A> where     A: PartialEq<B>,

fn eq(&self, other: &[B]) -> bool

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<'other, A, B> PartialEq<&'other [B]> for StableVec<A> where     A: PartialEq<B>,

fn eq(&self, other: &&'other [B]) -> bool

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A, B> PartialEq<Vec<B>> for StableVec<A> where     A: PartialEq<B>,

fn eq(&self, other: &Vec<B>) -> bool

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: Clone> Clone for StableVec<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for StableVec<T>

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

Formats the value using the given formatter.

impl<T> Index<usize> for StableVec<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 StableVec<T>

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

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

impl<T> FromIterator<T> for StableVec<T>

fn from_iter<I>(iter: I) -> Self where     I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl Write for StableVec<u8>

Write into StableVec<u8> by appending u8 elements. This is equivalent to calling push for each byte.

fn write(&mut self, buf: &[u8]) -> Result<usize>

Write a buffer into this writer, returning how many bytes were written.

fn write_all(&mut self, buf: &[u8]) -> Result<()>

Attempts to write an entire buffer into this writer.

fn flush(&mut self) -> Result<()>

Flush this output stream, ensuring that all intermediately buffered contents reach their destination.

fn write_fmt(&mut self, fmt: Arguments) -> Result<(), Error>

Writes a formatted string into this writer, returning any error encountered.

fn by_ref(&mut self) -> &mut Self

Creates a "by reference" adaptor for this instance of Write.