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, const B: usize, A> Clone for BTreeVec<T, B, A>

where T: Clone, A: Clone + Allocator,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

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> Ord for BTreeVec<T, B, A>

where T: Ord, A: Allocator,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T, const B: usize, A1, A2> PartialEq<BTreeVec<T, B, A2>> for BTreeVec<T, B, A1>

where T: PartialEq, A1: Allocator, A2: Allocator,

fn eq(&self, other: &BTreeVec<T, B, A2>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, const B: usize, A1, A2> PartialOrd<BTreeVec<T, B, A2>> for BTreeVec<T, B, A1>

where T: PartialOrd, A1: Allocator, A2: Allocator,

fn partial_cmp(&self, other: &BTreeVec<T, B, A2>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

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

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,