[−][src]Trait granite::ListStorage
Trait for list-like containers which can be the backing storage for data structures.
Safety
There's a number of invariants which have to be followed by the container:
- The length of the storage cannot be modified in the container when it's borrowed immutably or not borrowed at all;
new
andwith_capacity
must return empty storages, i.e. those which havelen() == 0
andis_empty() == true
;- it should be impossible for the length of the storage to overflow
isize
; - Calling
get_unchecked
orget_unchecked_mut
withself.len() > index
should not cause undefined behavior (otherwise, it may or may not — that is implementation specific); insert_and_fix
/remove_and_fix
call unsafe methods fromMoveFix
, meaning thatinsert
andremove
must be implemented according to the contract of the methods of that trait;- If an element is added at a position, it must be retrieveable in the exact same state as it was inserted until it is removed or modified using a method which explicitly does so.
Data structures may rely on those invariants for safety.
Associated Types
type Element
The type of values in the container.
Required methods
fn with_capacity(capacity: usize) -> Self
Creates an empty collection with the specified capacity.
Panics
Collections with a fixed capacity should panic if the specified capacity does not match their actual one, and are recommended to override the new
method to use the correct capacity.
fn insert(&mut self, index: usize, element: Self::Element)
Inserts an element at position index
within the collection, shifting all elements after it to the right.
Panics
Required to panic if index > len()
.
fn remove(&mut self, index: usize) -> Self::Element
Removes and returns the element at position index
within the vector, shifting all elements after it to the left.
Panics
Required to panic if the specified index does not exist.
fn len(&self) -> usize
Returns the number of elements in the collection, also referred to as its 'length'.
unsafe fn get_unchecked(&self, index: usize) -> &Self::Element
Returns a reference to the specified element in the collection, without doing bounds checking.
Safety
If the specified index is out of bounds, a dangling reference will be created, causing immediate undefined behavior.
unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element
Returns a mutable reference to the specified element in the collection, without doing bounds checking.
Safety
If the specified index is out of bounds, a dangling reference will be created, causing immediate undefined behavior.
Provided methods
fn get(&self, index: usize) -> Option<&Self::Element>
Returns a reference to the specified element in the collection, or None
if the index is out of bounds.
fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>
Returns a mutable reference to the specified element in the collection, or None
if the index is out of bounds.
fn new() -> Self
Creates a new empty collection. Dynamically-allocated collections created this way do not allocate memory.
Collections with fixed capacity should override this method to use the correct capacity, as the default implementation calls Self::with_capacity(0)
.
fn is_empty(&self) -> bool
Returns true
if the collection contains no elements, false
otherwise.
fn push(&mut self, element: Self::Element)
Appends an element to the back of the collection.
fn pop(&mut self) -> Option<Self::Element>
Removes the last element from the collection and returns it, or None
if it is empty.
fn capacity(&self) -> usize
Returns the amount of elements the collection can hold without requiring a memory allocation.
For collections which have a fixed capacity, this should be equal to the length; the default implementation uses exactly that.
fn reserve(&mut self, additional: usize)
Reserves capacity for at least additional more elements to be inserted in the given collection. The collection may reserve more space to avoid frequent reallocations. After calling reserve
, capacity
will be greater than or equal to self.len()
+ additional
. Does nothing if capacity is already sufficient.
For collections which have a fixed capacity, this should first check for the specified amount of elements to reserve for and if it's not zero, either reallocate the collection anew or, if that is not supported, panic. The default implementation does exactly that.
fn shrink_to_fit(&mut self)
Shrinks the capacity of the collection as much as possible.
It will drop down as close as possible to the current length, though dynamically allocated collections may not always reallocate exactly as much as it is needed to store all elements and none more.
The default implementation does nothing.
fn truncate(&mut self, len: usize)
Shortens the collection, keeping the first len
elements and dropping the rest.
If len
is greater than the collection's current length, this has no effect.
Note that this method has no effect on the allocated capacity of the collection.
fn insert_and_shiftfix(&mut self, index: usize, element: Self::Element) where
Self::Element: MoveFix,
Self::Element: MoveFix,
Inserts an element at position index
within the collection. The items after the inserted item should be notified using the MoveFix
trait or not have their indices changed at all (index changes are not guaranteed and this behavior is implementation-dependent).
Panics
Same as insert
.
fn remove_and_shiftfix(&mut self, index: usize) -> Self::Element where
Self::Element: MoveFix,
Self::Element: MoveFix,
Removes and returns the element at position index
within the collection. The items after the inserted item should be notified using the MoveFix
trait or not change indicies at all (index changes are not guaranteed and this behavior is implementation-dependent).
Panics
Same as remove
.
fn add(&mut self, element: Self::Element) -> usize
Adds an element to the collection at an arbitrary index, returning that index. Will never shift elements around. The default implementation will call push
and return the index of the element pushed.
This method is used instead of push
by data structures. It is overriden by SparseStorage
with the use of a free-list for placing new elements in place of old holes.
Implementations on Foreign Types
impl<T> ListStorage for Vec<T>
[src]
type Element = T
fn with_capacity(capacity: usize) -> Self
[src]
fn insert(&mut self, index: usize, element: Self::Element)
[src]
fn remove(&mut self, index: usize) -> Self::Element
[src]
fn len(&self) -> usize
[src]
unsafe fn get_unchecked(&self, index: usize) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element
[src]
fn get(&self, index: usize) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>
[src]
fn new() -> Self
[src]
fn push(&mut self, element: Self::Element)
[src]
fn pop(&mut self) -> Option<Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
fn truncate(&mut self, len: usize)
[src]
impl<T> ListStorage for VecDeque<T>
[src]
type Element = T
fn with_capacity(capacity: usize) -> Self
[src]
fn insert(&mut self, index: usize, element: Self::Element)
[src]
fn remove(&mut self, index: usize) -> Self::Element
[src]
fn len(&self) -> usize
[src]
unsafe fn get_unchecked(&self, index: usize) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element
[src]
fn get(&self, index: usize) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>
[src]
fn push(&mut self, element: Self::Element)
[src]
fn pop(&mut self) -> Option<Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
fn truncate(&mut self, len: usize)
[src]
impl<A> ListStorage for ArrayVec<A> where
A: Array,
[src]
A: Array,
type Element = A::Item
fn with_capacity(capacity: usize) -> Self
[src]
fn insert(&mut self, index: usize, element: Self::Element)
[src]
fn remove(&mut self, index: usize) -> Self::Element
[src]
fn len(&self) -> usize
[src]
unsafe fn get_unchecked(&self, index: usize) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element
[src]
fn get(&self, index: usize) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>
[src]
fn new() -> Self
[src]
fn push(&mut self, element: Self::Element)
[src]
fn pop(&mut self) -> Option<Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
fn truncate(&mut self, len: usize)
[src]
impl<A> ListStorage for SmallVec<A> where
A: Array,
[src]
A: Array,
type Element = A::Item
fn with_capacity(capacity: usize) -> Self
[src]
fn insert(&mut self, index: usize, element: Self::Element)
[src]
fn remove(&mut self, index: usize) -> Self::Element
[src]
fn len(&self) -> usize
[src]
unsafe fn get_unchecked(&self, index: usize) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element
[src]
fn get(&self, index: usize) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>
[src]
fn new() -> Self
[src]
fn push(&mut self, element: Self::Element)
[src]
fn pop(&mut self) -> Option<Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
fn truncate(&mut self, len: usize)
[src]
Implementors
impl<E, S> ListStorage for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
type Element = E
fn with_capacity(capacity: usize) -> Self
[src]
fn insert(&mut self, index: usize, element: Self::Element)
[src]
fn remove(&mut self, index: usize) -> Self::Element
[src]
fn len(&self) -> usize
[src]
unsafe fn get_unchecked(&self, index: usize) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element
[src]
fn get(&self, index: usize) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>
[src]
fn new() -> Self
[src]
fn push(&mut self, element: Self::Element)
[src]
fn pop(&mut self) -> Option<Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
fn truncate(&mut self, len: usize)
[src]
fn insert_and_shiftfix(&mut self, index: usize, element: Self::Element) where
Self::Element: MoveFix,
[src]
Self::Element: MoveFix,
fn remove_and_shiftfix(&mut self, index: usize) -> Self::Element where
Self::Element: MoveFix,
[src]
Self::Element: MoveFix,