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>

fn new() -> Self

Constructs a new, empty StableVec<T>.

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

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.

fn reserve(&mut self, additional: usize)

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

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(&'♥'));

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.

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

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].

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].

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

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.

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!

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!

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());

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);

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());

fn capacity(&self) -> usize

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

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);

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);
}

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. Furthermore, you can remove elements from the stable vector during iteration by calling remove_current() on the iterator object.

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 &[_]);

As mentioned above, you can remove elements from the stable vector while iterating over it. But you can't use a for-loop in this case.

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

{
    let mut it = sv.iter_mut();
    while let Some(e) = it.next() {
        if *e == 2.0 {
            it.remove_current();
        }
        *e *= 2.0;
    }
}

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

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);
}

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'));

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']);

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

Retains only the elements specified by the given predicate.

Each element e for which predicate(&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 &[_]);

Trait Implementations

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

fn clone(&self) -> StableVec<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

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

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

This method tests for !=.

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> 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> Default for StableVec<T>

fn default() -> Self

Returns the "default value" for a type.

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

fn from(slice: S) -> Self

Performs the conversion.

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<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<'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: Debug> Debug for StableVec<T>

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

Formats the value using the given formatter.

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 ==.

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 ==.

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 ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.