Struct BTreeVec

pub struct BTreeVec<T, const B: usize = 12, A: Allocator = Global> { /* private fields */ }

A growable array (vector) implemented as a B+ tree.

Provides non-amortized O(log n) random accesses, insertions, and removals, and O(n) iteration.

B is the branching factor. It must be at least 3. The standard library uses a value of 6 for its B-tree structures. Larger values are better when T is smaller.

Mathematical variables

For the purposes of specifying the time complexity of various operations, n refers to the number of items in the vector.

Implementations

impl<T> BTreeVec<T>

pub fn new() -> Self

Creates a new BTreeVec. Note that this function is implemented only for the default value of B; see Self::create for an equivalent that works with all values of B.

impl<T, A: Allocator> BTreeVec<T, 12, A>

pub fn new_in(alloc: A) -> Self

Creates a new BTreeVec with the given allocator. Note that this function is implemented only for the default value of B; see Self::create_in for an equivalent that works with all values of B.

impl<T, const B: usize> BTreeVec<T, B>

pub fn create() -> Self

Creates a new BTreeVec. This function exists because BTreeVec::new is implemented only for the default value of B.

impl<T, const B: usize, A: Allocator> BTreeVec<T, B, A>

pub fn create_in(alloc: A) -> Self

Creates a new BTreeVec with the given allocator. This function exists because BTreeVec::new_in is implemented only for the default value of B.

pub fn len(&self) -> usize

Gets the length of the vector.

Time complexity

Constant.

pub fn is_empty(&self) -> bool

Checks whether the vector is empty.

Time complexity

Constant.

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

Gets the item at index, or None if no such item exists.

Time complexity

Θ(log n).

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

Gets a mutable reference to the item at index, or None if no such item exists.

Time complexity

Θ(log n).

pub fn first(&self) -> Option<&T>

Gets the first item in the vector, or None if the vector is empty.

Time complexity

Θ(log n).

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

Gets a mutable reference to the first item in the vector, or None if the vector is empty.

Time complexity

Θ(log n).

pub fn last(&self) -> Option<&T>

Gets the last item in the vector, or None if the vector is empty.

Time complexity

Θ(log n).

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

Gets a mutable reference to the last item in the vector, or None if the vector is empty.

Time complexity

Θ(log n).

pub fn insert(&mut self, index: usize, item: T)

Inserts item at index.

Panics

Panics if index is greater than self.len().

Time complexity

Θ(log n).

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

Inserts item at the end of the vector.

Time complexity

Θ(log n).

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

Removes and returns the item at index.

Panics

Panics if index is not less than self.len().

Time complexity

Θ(log n).

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

Removes and returns the last item in the vector, or None if the vector is empty.

Time complexity

Θ(log n).

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

Gets an iterator that returns references to each item in the vector.

Time complexity

Iteration over the entire vector is Θ(n).

pub fn iter_mut(&mut self) -> IterMut<'_, T, B>

Gets an iterator that returns mutable references to each item in the vector.

Time complexity

Iteration over the entire vector is Θ(n).

Trait Implementations

impl<T: Debug, const B: usize, A: Allocator> Debug for BTreeVec<T, B, A>

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

Formats the value using the given formatter.

impl<T, const B: usize, A> Default for BTreeVec<T, B, A>

where A: Allocator + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T, const B: usize, A> Drop for BTreeVec<T, B, A>

where A: Allocator,

fn drop(&mut self)

Executes the destructor for this type.

impl<T, const B: usize, A: Allocator> Index<usize> for BTreeVec<T, B, A>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T, const B: usize, A: Allocator> IndexMut<usize> for BTreeVec<T, B, A>

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

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

impl<'a, T, const B: usize, A> IntoIterator for &'a BTreeVec<T, B, A>

where A: Allocator,

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T, B>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T, const B: usize, A> IntoIterator for &'a mut BTreeVec<T, B, A>

where A: Allocator,

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T, B>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const B: usize, A: Allocator> IntoIterator for BTreeVec<T, B, A>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, B, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const B: usize, A> Send for BTreeVec<T, B, A>

where T: Send, A: Allocator,

impl<T, const B: usize, A> Sync for BTreeVec<T, B, A>

where T: Sync, A: Allocator,