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]
fn new() -> Self
[src]
Constructs a new, empty StableVec<T>
.
The stable-vector will not allocate until elements are pushed onto it.
fn with_capacity(capacity: usize) -> Self
[src]
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)
[src]
Reserves capacity for at least additional
more elements to be
inserted.
fn push(&mut self, elem: T) -> usize
[src]
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>
[src]
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>
[src]
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>
[src]
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>
[src]
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
[src]
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)
[src]
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)
[src]
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)
[src]
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
[src]
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
[src]
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
[src]
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
[src]
Returns the number of elements the stable-vector can hold without reallocating.
fn next_index(&self) -> usize
[src]
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>
[src]
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>
[src]
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
[src]
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>,
[src]
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>
[src]
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,
[src]
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>
[src]
fn clone(&self) -> StableVec<T>
[src]
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<T: PartialEq> PartialEq for StableVec<T>
[src]
fn eq(&self, __arg_0: &StableVec<T>) -> bool
[src]
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, __arg_0: &StableVec<T>) -> bool
[src]
This method tests for !=
.
impl<T: Eq> Eq for StableVec<T>
[src]
impl<T> Drop for StableVec<T>
[src]
impl<T> Index<usize> for StableVec<T>
[src]
type Output = T
The returned type after indexing.
fn index(&self, index: usize) -> &T
[src]
Performs the indexing (container[index]
) operation.
impl<T> IndexMut<usize> for StableVec<T>
[src]
fn index_mut(&mut self, index: usize) -> &mut T
[src]
Performs the mutable indexing (container[index]
) operation.
impl<T> Default for StableVec<T>
[src]
impl<T, S> From<S> for StableVec<T> where
S: AsRef<[T]>,
T: Clone,
[src]
S: AsRef<[T]>,
T: Clone,
impl<T> FromIterator<T> for StableVec<T>
[src]
fn from_iter<I>(iter: I) -> Self where
I: IntoIterator<Item = T>,
[src]
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more
impl<T> Extend<T> for StableVec<T>
[src]
fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = T>,
[src]
I: IntoIterator<Item = T>,
Extends a collection with the contents of an iterator. Read more
impl<'a, T> IntoIterator for &'a StableVec<T>
[src]
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]
Creates an iterator from a value. Read more
impl<'a, T> IntoIterator for &'a mut StableVec<T>
[src]
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]
Creates an iterator from a value. Read more
impl<T: Debug> Debug for StableVec<T>
[src]
impl<A, B> PartialEq<[B]> for StableVec<A> where
A: PartialEq<B>,
[src]
A: PartialEq<B>,
fn eq(&self, other: &[B]) -> bool
[src]
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]
This method tests for !=
.
impl<'other, A, B> PartialEq<&'other [B]> for StableVec<A> where
A: PartialEq<B>,
[src]
A: PartialEq<B>,
fn eq(&self, other: &&'other [B]) -> bool
[src]
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]
This method tests for !=
.
impl<A, B> PartialEq<Vec<B>> for StableVec<A> where
A: PartialEq<B>,
[src]
A: PartialEq<B>,