Struct ExtensibleArray 

pub struct ExtensibleArray<T> { /* private fields */ }

Growable array as described by Moffat and Mackenzie.

Implementations

impl<T> ExtensibleArray<T>

pub fn new() -> Self

Return an empty extensible array with zero capacity.

Note that pre-allocating capacity has no benefit with this data structure since append operations are always constant time and no reallocation and copy is ever performed.

pub fn push(&mut self, value: T)

Appends an element to the back of a collection.

Panics

Panics if a new segment is allocated that would exceed isize::MAX bytes.

Time complexity

Constant time.

pub fn push_within_capacity(&mut self, value: T) -> Result<(), T>

Appends an element if there is sufficient spare capacity, otherwise an error is returned with the element.

Time complexity

Constant time.

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

Removes the last element from an array and returns it, or None if it is empty.

Time complexity

Constant time.

pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T>

Removes and returns the last element from a vector if the predicate returns true, or None if the predicate returns false or the vector is empty (the predicate will not be called in that case).

Time complexity

Constant time.

pub fn len(&self) -> usize

Return the number of elements in the array.

Time complexity

Constant time.

pub fn capacity(&self) -> usize

Returns the total number of elements the extensible array can hold without reallocating.

Time complexity

log2(count)/2

pub fn is_empty(&self) -> bool

Returns true if the array has a length of 0.

Time complexity

Constant time.

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

Retrieve a reference to the element at the given offset.

Time complexity

Constant time.

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

Returns a mutable reference to an element.

Time complexity

Constant time.

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

Removes an element from the vector and returns it.

The removed element is replaced by the last element of the vector.

This does not preserve ordering of the remaining elements.

Time complexity

Constant time.

pub fn iter(&self) -> ExtArrayIter<'_, T>

Returns an iterator over the extensible array.

The iterator yields all items from start to end.

pub fn clear(&mut self)

Clears the extensible array, removing and dropping all values and deallocating all previously allocated segments.

Time complexity

O(n) if elements are droppable, otherwise O(sqrt(n))

Trait Implementations

impl<T> Default for ExtensibleArray<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Display for ExtensibleArray<T>

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

Formats the value using the given formatter.

impl<T> Drop for ExtensibleArray<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<A> FromIterator<A> for ExtensibleArray<A>

fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self

Creates a value from an iterator.

impl<T> Index<usize> for ExtensibleArray<T>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for ExtensibleArray<T>

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

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

impl<T> IntoIterator for ExtensibleArray<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = ExtArrayIntoIter<<ExtensibleArray<T> as IntoIterator>::Item>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.