Struct stable_vec::StableVec [−][src]
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:
- It has a linear O(n) time complexity
- 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
Adding and removing elements
Accessing elements
get()
(returnsOption<&T>
)- the
[]
index operator (returns&T
) get_mut()
(returnsOption<&mut T>
)- the mutable
[]
index operator (returns&mut T
) remove()
(returnsOption<T>
)
Stable vector specific
Number of elements
Capacity management
Methods
impl<T> StableVec<T>
[src]
impl<T> StableVec<T>
pub fn new() -> Self
[src]
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
[src]
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
[src]
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)
[src]
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
[src]
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>
[src]
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>
[src]
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)
[src]
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>
[src]
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>
[src]
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>
[src]
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
[src]
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)
[src]
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)
[src]
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)
[src]
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
[src]
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
[src]
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
[src]
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)
[src]
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
[src]
pub fn capacity(&self) -> usize
Returns the number of elements the stable-vector can hold without reallocating.
pub fn next_index(&self) -> usize
[src]
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>pub fn iter(&self) -> Iter<T>
[src]
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>pub fn iter_mut(&mut self) -> IterMut<T>
[src]
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. 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 &[_]);
ⓘImportant traits for Keys<'a>pub fn keys(&self) -> Keys
[src]
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>,
[src]
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>
[src]
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, predicate: P) where
P: FnMut(&T) -> bool,
[src]
pub 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 &[_]);
pub fn extend_from_slice(&mut self, new_elements: &[T]) where
T: Clone,
[src]
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: Clone> Clone for StableVec<T>
[src]
impl<T: Clone> Clone for StableVec<T>
fn clone(&self) -> StableVec<T>
[src]
fn clone(&self) -> StableVec<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<T: PartialEq> PartialEq for StableVec<T>
[src]
impl<T: PartialEq> PartialEq for StableVec<T>
fn eq(&self, other: &StableVec<T>) -> bool
[src]
fn eq(&self, other: &StableVec<T>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &StableVec<T>) -> bool
[src]
fn ne(&self, other: &StableVec<T>) -> bool
This method tests for !=
.
impl<T: Eq> Eq for StableVec<T>
[src]
impl<T: Eq> Eq for StableVec<T>
impl<T> Drop for StableVec<T>
[src]
impl<T> Drop for StableVec<T>
impl<T> Index<usize> for StableVec<T>
[src]
impl<T> Index<usize> for StableVec<T>
type Output = T
The returned type after indexing.
fn index(&self, index: usize) -> &T
[src]
fn index(&self, index: usize) -> &T
Performs the indexing (container[index]
) operation.
impl<T> IndexMut<usize> for StableVec<T>
[src]
impl<T> IndexMut<usize> for StableVec<T>
fn index_mut(&mut self, index: usize) -> &mut T
[src]
fn index_mut(&mut self, index: usize) -> &mut T
Performs the mutable indexing (container[index]
) operation.
impl<T> Default for StableVec<T>
[src]
impl<T> Default for StableVec<T>
impl<T, S> From<S> for StableVec<T> where
S: AsRef<[T]>,
T: Clone,
[src]
impl<T, S> From<S> for StableVec<T> where
S: AsRef<[T]>,
T: Clone,
impl<T> FromIterator<T> for StableVec<T>
[src]
impl<T> FromIterator<T> for StableVec<T>
fn from_iter<I>(iter: I) -> Self where
I: IntoIterator<Item = T>,
[src]
fn from_iter<I>(iter: I) -> Self where
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more
impl<T> Extend<T> for StableVec<T>
[src]
impl<T> Extend<T> for StableVec<T>
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = T>,
[src]
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = T>,
Extends a collection with the contents of an iterator. Read more
impl Write for StableVec<u8>
[src]
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>
[src]
fn write(&mut self, buf: &[u8]) -> Result<usize>
Write a buffer into this object, returning how many bytes were written. Read more
fn write_all(&mut self, buf: &[u8]) -> Result<()>
[src]
fn write_all(&mut self, buf: &[u8]) -> Result<()>
Attempts to write an entire buffer into this write. Read more
fn flush(&mut self) -> Result<()>
[src]
fn flush(&mut self) -> Result<()>
Flush this output stream, ensuring that all intermediately buffered contents reach their destination. Read more
fn write_fmt(&mut self, fmt: Arguments) -> Result<(), Error>
1.0.0[src]
fn write_fmt(&mut self, fmt: Arguments) -> Result<(), Error>
Writes a formatted string into this writer, returning any error encountered. Read more
fn by_ref(&mut self) -> &mut Self
1.0.0[src]
fn by_ref(&mut self) -> &mut Self
Creates a "by reference" adaptor for this instance of Write
. Read more
impl<'a, T> IntoIterator for &'a StableVec<T>
[src]
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
[src]
fn into_iter(self) -> Self::IntoIter
Creates an iterator from a value. Read more
impl<'a, T> IntoIterator for &'a mut StableVec<T>
[src]
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
[src]
fn into_iter(self) -> Self::IntoIter
Creates an iterator from a value. Read more
impl<T: Debug> Debug for StableVec<T>
[src]
impl<T: Debug> Debug for StableVec<T>
fn fmt(&self, f: &mut Formatter) -> Result
[src]
fn fmt(&self, f: &mut Formatter) -> Result
Formats the value using the given formatter. Read more
impl<A, B> PartialEq<[B]> for StableVec<A> where
A: PartialEq<B>,
[src]
impl<A, B> PartialEq<[B]> for StableVec<A> where
A: PartialEq<B>,
fn eq(&self, other: &[B]) -> bool
[src]
fn eq(&self, other: &[B]) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
fn ne(&self, other: &Rhs) -> bool
This method tests for !=
.
impl<'other, A, B> PartialEq<&'other [B]> for StableVec<A> where
A: PartialEq<B>,
[src]
impl<'other, A, B> PartialEq<&'other [B]> for StableVec<A> where
A: PartialEq<B>,
fn eq(&self, other: &&'other [B]) -> bool
[src]
fn eq(&self, other: &&'other [B]) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
fn ne(&self, other: &Rhs) -> bool
This method tests for !=
.
impl<A, B> PartialEq<Vec<B>> for StableVec<A> where
A: PartialEq<B>,
[src]
impl<A, B> PartialEq<Vec<B>> for StableVec<A> where
A: PartialEq<B>,