# Struct im::vector::Vector [−][src]

pub struct Vector<A> { /* fields omitted */ }

A persistent vector.

This is a sequence of elements in insertion order - if you need a list of things, any kind of list of things, this is what you're looking for.

It's implemented as an RRB vector with smart
head/tail chunking. In performance terms, this means
that practically every operation is O(log n), except push/pop on
both sides, which will be O(1) amortised, and O(log n) in the
worst case. In practice, the push/pop operations will be
blindingly fast, nearly on par with the native
`VecDeque`

, and other operations will have decent, if
not high, performance, but they all have more or less the same
O(log n) complexity, so you don't need to keep their performance
characteristics in mind - everything, even splitting and merging,
is safe to use and never too slow.

## Performance Notes

Because of the head/tail chunking technique, until you push a
number of items above double the tree's branching factor (that's
`self.len()`

= 2 × *k* (where *k* = 64) = 128) on either side, the
data structure is still just a handful of arrays, not yet an RRB
tree, so you'll see performance and memory characteristics similar
to `Vec`

or `VecDeque`

.

This means that the structure always preallocates four chunks of
size *k* (*k* being the tree's branching factor), equivalent to a
`Vec`

with an initial capacity of 256. Beyond that, it will
allocate tree nodes of capacity *k* as needed.

## Methods

`impl<A: Clone> Vector<A>`

[src]

`impl<A: Clone> Vector<A>`

`pub fn new() -> Self`

[src]

`pub fn new() -> Self`

Construct an empty vector.

`pub fn singleton(a: A) -> Self`

[src]

`pub fn singleton(a: A) -> Self`

Construct a vector with a single value.

`pub fn len(&self) -> usize`

[src]

`pub fn len(&self) -> usize`

`pub fn is_empty(&self) -> bool`

[src]

`pub fn is_empty(&self) -> bool`

Test whether a vector is empty.

Time: O(1)

# Examples

let vec = vector!["Joe", "Mike", "Robert"]; assert_eq!(false, vec.is_empty()); assert_eq!(true, Vector::<i32>::new().is_empty());

#### ⓘImportant traits for Iter<'a, A>`pub fn iter(&self) -> Iter<A>`

[src]

`pub fn iter(&self) -> Iter<A>`

Get an iterator over a vector.

Time: O(1)

#### ⓘImportant traits for IterMut<'a, A>`pub fn iter_mut(&mut self) -> IterMut<A>`

[src]

`pub fn iter_mut(&mut self) -> IterMut<A>`

Get a mutable iterator over a vector.

Time: O(1)

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

[src]

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

Get a reference to the value at index `index`

in a vector.

Returns `None`

if the index is out of bounds.

Time: O(log n)

# Examples

let vec = vector!["Joe", "Mike", "Robert"]; assert_eq!(Some(&"Robert"), vec.get(2)); assert_eq!(None, vec.get(5));

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

[src]

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

Get a mutable reference to the value at index `index`

in a
vector.

Returns `None`

if the index is out of bounds.

Time: O(log n)

# Examples

let mut vec = vector!["Joe", "Mike", "Robert"]; { let robert = vec.get_mut(2).unwrap(); assert_eq!(&mut "Robert", robert); *robert = "Bjarne"; } assert_eq!(vector!["Joe", "Mike", "Bjarne"], vec);

`pub fn front(&self) -> Option<&A>`

[src]

`pub fn front(&self) -> Option<&A>`

Get the first element of a vector.

If the vector is empty, `None`

is returned.

Time: O(log n)

`pub fn front_mut(&mut self) -> Option<&mut A>`

[src]

`pub fn front_mut(&mut self) -> Option<&mut A>`

Get a mutable reference to the first element of a vector.

If the vector is empty, `None`

is returned.

Time: O(log n)

`pub fn head(&self) -> Option<&A>`

[src]

`pub fn head(&self) -> Option<&A>`

Get the first element of a vector.

If the vector is empty, `None`

is returned.

This is an alias for the `front`

method.

Time: O(log n)

`pub fn back(&self) -> Option<&A>`

[src]

`pub fn back(&self) -> Option<&A>`

Get the last element of a vector.

If the vector is empty, `None`

is returned.

Time: O(log n)

`pub fn back_mut(&mut self) -> Option<&mut A>`

[src]

`pub fn back_mut(&mut self) -> Option<&mut A>`

Get a mutable reference to the last element of a vector.

If the vector is empty, `None`

is returned.

Time: O(log n)

`pub fn last(&self) -> Option<&A>`

[src]

`pub fn last(&self) -> Option<&A>`

Get the last element of a vector.

If the vector is empty, `None`

is returned.

This is an alias for the `back`

method.

Time: O(log n)

`pub fn index_of(&self, value: &A) -> Option<usize> where`

A: PartialEq,

[src]

`pub fn index_of(&self, value: &A) -> Option<usize> where`

A: PartialEq,

Get the index of a given element in the vector.

Searches the vector for the first occurrence of a given value,
and returns the index of the value if it's there. Otherwise,
it returns `None`

.

Time: O(n)

# Examples

let mut vec = vector![1, 2, 3, 4, 5]; assert_eq!(Some(2), vec.index_of(&3)); assert_eq!(None, vec.index_of(&31337));

`pub fn contains(&self, value: &A) -> bool where`

A: PartialEq,

[src]

`pub fn contains(&self, value: &A) -> bool where`

A: PartialEq,

Test if a given element is in the vector.

Searches the vector for the first occurrence of a given value,
and returns `true if it's there. If it's nowhere to be found in the vector, it returns`

false`.

Time: O(n)

# Examples

let mut vec = vector![1, 2, 3, 4, 5]; assert_eq!(true, vec.contains(&3)); assert_eq!(false, vec.contains(&31337));

`pub fn update(&self, index: usize, value: A) -> Self`

[src]

`pub fn update(&self, index: usize, value: A) -> Self`

Create a new vector with the value at index `index`

updated.

Panics if the index is out of bounds.

Time: O(log n)

# Examples

let mut vec = vector![1, 2, 3]; assert_eq!(vector![1, 5, 3], vec.update(1, 5));

`pub fn set(&mut self, index: usize, value: A)`

[src]

`pub fn set(&mut self, index: usize, value: A)`

Update the value at index `index`

in a vector.

Panics if the index is out of bounds.

Time: O(log n)

`pub fn swap(&mut self, i: usize, j: usize)`

[src]

`pub fn swap(&mut self, i: usize, j: usize)`

Swaps the elements at indices `i`

and `j`

.

Time: O(log n)

`pub fn push_front(&mut self, value: A)`

[src]

`pub fn push_front(&mut self, value: A)`

Push a value to the front of a vector.

Time: O(1)*

# Examples

let mut vec = vector![5, 6, 7]; vec.push_front(4); assert_eq!(vector![4, 5, 6, 7], vec);

`pub fn push_back(&mut self, value: A)`

[src]

`pub fn push_back(&mut self, value: A)`

Push a value to the back of a vector.

Time: O(1)*

# Examples

let mut vec = vector![1, 2, 3]; vec.push_back(4); assert_eq!(vector![1, 2, 3, 4], vec);

`pub fn pop_front(&mut self) -> Option<A>`

[src]

`pub fn pop_front(&mut self) -> Option<A>`

Remove the first element from a vector and return it.

Time: O(1)*

# Examples

let mut vec = vector![1, 2, 3]; assert_eq!(Some(1), vec.pop_front()); assert_eq!(vector![2, 3], vec);

`pub fn pop_back(&mut self) -> Option<A>`

[src]

`pub fn pop_back(&mut self) -> Option<A>`

Remove the last element from a vector and return it.

Time: O(1)*

# Examples

let mut vec = vector![1, 2, 3]; assert_eq!(Some(3), vec.pop_back()); assert_eq!(vector![1, 2], vec);

`pub fn append(&mut self, other: Self)`

[src]

`pub fn append(&mut self, other: Self)`

Append the vector `other`

to the end of the current vector.

Time: O(log n)

# Examples

let mut vec = vector![1, 2, 3]; vec.append(vector![7, 8, 9]); assert_eq!(vector![1, 2, 3, 7, 8, 9], vec);

`pub fn retain<F>(&mut self, f: F) where`

F: FnMut(&A) -> bool,

[src]

`pub fn retain<F>(&mut self, f: F) where`

F: FnMut(&A) -> bool,

Retain only the elements specified by the predicate.

Remove all elements for which the provided function `f`

returns false from the vector.

Time: O(n)

`pub fn split_at(self, index: usize) -> (Self, Self)`

[src]

`pub fn split_at(self, index: usize) -> (Self, Self)`

Split a vector at a given index.

Split a vector at a given index, consuming the vector and returning a pair of the left hand side and the right hand side of the split.

Time: O(log n)

# Examples

let mut vec = vector![1, 2, 3, 7, 8, 9]; let (left, right) = vec.split_at(3); assert_eq!(vector![1, 2, 3], left); assert_eq!(vector![7, 8, 9], right);

`pub fn split_off(&mut self, index: usize) -> Self`

[src]

`pub fn split_off(&mut self, index: usize) -> Self`

Split a vector at a given index.

Split a vector at a given index, leaving the left hand side in the current vector and returning a new vector containing the right hand side.

Time: O(log n)

# Examples

let mut left = vector![1, 2, 3, 7, 8, 9]; let right = left.split_off(3); assert_eq!(vector![1, 2, 3], left); assert_eq!(vector![7, 8, 9], right);

`pub fn skip(&self, count: usize) -> Self`

[src]

`pub fn skip(&self, count: usize) -> Self`

Construct a vector with `count`

elements removed from the
start of the current vector.

Time: O(log n)

`pub fn take(&self, count: usize) -> Self`

[src]

`pub fn take(&self, count: usize) -> Self`

Construct a vector of the first `count`

elements from the
current vector.

Time: O(log n)

`pub fn truncate(&mut self, len: usize)`

[src]

`pub fn truncate(&mut self, len: usize)`

Truncate a vector to the given size.

Discards all elements in the vector beyond the given length.

Panics if the new length is greater than the current length.

Time: O(log n)

`pub fn insert(&mut self, index: usize, value: A)`

[src]

`pub fn insert(&mut self, index: usize, value: A)`

Insert an element into a vector.

Insert an element at position `index`

, shifting all elements
after it to the right.

## Performance Note

While `push_front`

and `push_back`

are heavily optimised
operations, `insert`

in the middle of a vector requires a
split, a push, and an append. Thus, if you want to insert
many elements at the same location, instead of `insert`

ing
them one by one, you should rather create a new vector
containing the elements to insert, split the vector at the
insertion point, and append the left hand, the new vector and
the right hand in order.

Time: O(log n)

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

[src]

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

Remove an element from a vector.

Remove the element from position 'index', shifting all elements after it to the left, and return the removec element.

## Performance Note

While `pop_front`

and `pop_back`

are heavily optimised
operations, `remove`

in the middle of a vector requires a
split, a pop, and an append. Thus, if you want to remove many
elements from the same location, instead of `remove`

ing them
one by one, it is much better to use `slice`

.

Time: O(log n)

`pub fn clear(&mut self)`

[src]

`pub fn clear(&mut self)`

Discard all elements from the vector.

This leaves you with an empty vector, and all elements that were previously inside it are dropped.

Time: O(n)

`pub fn binary_search_by<F>(&self, f: F) -> Result<usize, usize> where`

F: FnMut(&A) -> Ordering,

[src]

`pub fn binary_search_by<F>(&self, f: F) -> Result<usize, usize> where`

F: FnMut(&A) -> Ordering,

Binary search a sorted vector for a given element using a comparator function.

Assumes the vector has already been sorted using the same comparator
function, eg. by using `sort_by`

.

If the value is found, it returns `Ok(index)`

where `index`

is the index
of the element. If the value isn't found, it returns `Err(index)`

where
`index`

is the index at which the element would need to be inserted to
maintain sorted order.

Time: O(log n)

`pub fn binary_search(&self, value: &A) -> Result<usize, usize> where`

A: Ord,

[src]

`pub fn binary_search(&self, value: &A) -> Result<usize, usize> where`

A: Ord,

Binary search a sorted vector for a given element.

If the value is found, it returns `Ok(index)`

where `index`

is the index
of the element. If the value isn't found, it returns `Err(index)`

where
`index`

is the index at which the element would need to be inserted to
maintain sorted order.

Time: O(log n)

`pub fn binary_search_by_key<B, F>(&self, b: &B, f: F) -> Result<usize, usize> where`

F: FnMut(&A) -> B,

B: Ord,

[src]

`pub fn binary_search_by_key<B, F>(&self, b: &B, f: F) -> Result<usize, usize> where`

F: FnMut(&A) -> B,

B: Ord,

Binary search a sorted vector for a given element with a key extract function.

Assumes the vector has already been sorted using the same key extract
function, eg. by using `sort_by_key`

.

If the value is found, it returns `Ok(index)`

where `index`

is the index
of the element. If the value isn't found, it returns `Err(index)`

where
`index`

is the index at which the element would need to be inserted to
maintain sorted order.

Time: O(log n)

`pub fn insert_ord(&mut self, item: A) where`

A: Ord,

[src]

`pub fn insert_ord(&mut self, item: A) where`

A: Ord,

Insert an element into a sorted vector.

Insert an element into a vector in sorted order, assuming the vector is already in sorted order.

Time: O(log n)

# Examples

let mut vec = vector![1, 2, 3, 7, 8, 9]; vec.insert_ord(5); assert_eq!(vector![1, 2, 3, 5, 7, 8, 9], vec);

`pub fn sort(&mut self) where`

A: Ord,

[src]

`pub fn sort(&mut self) where`

A: Ord,

Sort a vector.

Time: O(n log n)

# Examples

let mut vec = vector![3, 2, 5, 4, 1]; vec.sort(); assert_eq!(vector![1, 2, 3, 4, 5], vec);

`pub fn sort_by<F>(&mut self, cmp: F) where`

F: Fn(&A, &A) -> Ordering,

[src]

`pub fn sort_by<F>(&mut self, cmp: F) where`

F: Fn(&A, &A) -> Ordering,

Sort a vector using a comparator function.

Time: O(n log n)

# Examples

let mut vec = vector![3, 2, 5, 4, 1]; vec.sort_by(|left, right| left.cmp(right)); assert_eq!(vector![1, 2, 3, 4, 5], vec);

## Trait Implementations

`impl<A: Clone> Default for Vector<A>`

[src]

`impl<A: Clone> Default for Vector<A>`

`impl<A> Clone for Vector<A>`

[src]

`impl<A> Clone for Vector<A>`

`fn clone(&self) -> Self`

[src]

`fn clone(&self) -> Self`

Returns a copy of the value. Read more

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

1.0.0[src]

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

Performs copy-assignment from `source`

. Read more

`impl<A: Clone + Debug> Debug for Vector<A>`

[src]

`impl<A: Clone + Debug> Debug for Vector<A>`

`fn fmt(&self, f: &mut Formatter) -> Result<(), Error>`

[src]

`fn fmt(&self, f: &mut Formatter) -> Result<(), Error>`

Formats the value using the given formatter. Read more

`impl<A: Clone + PartialEq> PartialEq for Vector<A>`

[src]

`impl<A: Clone + PartialEq> PartialEq for Vector<A>`

`fn eq(&self, other: &Self) -> bool`

[src]

`fn eq(&self, other: &Self) -> bool`

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]

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

This method tests for `!=`

.

`impl<A: Clone + Eq> Eq for Vector<A>`

[src]

`impl<A: Clone + Eq> Eq for Vector<A>`

`impl<A: Clone + PartialOrd> PartialOrd for Vector<A>`

[src]

`impl<A: Clone + PartialOrd> PartialOrd for Vector<A>`

`fn partial_cmp(&self, other: &Self) -> Option<Ordering>`

[src]

`fn partial_cmp(&self, other: &Self) -> Option<Ordering>`

This method returns an ordering between `self`

and `other`

values if one exists. Read more

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

1.0.0[src]

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

This method tests less than (for `self`

and `other`

) and is used by the `<`

operator. Read more

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

1.0.0[src]

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

This method tests less than or equal to (for `self`

and `other`

) and is used by the `<=`

operator. Read more

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

1.0.0[src]

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

This method tests greater than (for `self`

and `other`

) and is used by the `>`

operator. Read more

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

1.0.0[src]

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

This method tests greater than or equal to (for `self`

and `other`

) and is used by the `>=`

operator. Read more

`impl<A: Clone + Ord> Ord for Vector<A>`

[src]

`impl<A: Clone + Ord> Ord for Vector<A>`

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

[src]

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

This method returns an `Ordering`

between `self`

and `other`

. Read more

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

1.21.0[src]

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

Compares and returns the maximum of two values. Read more

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

1.21.0[src]

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

Compares and returns the minimum of two values. Read more

`impl<A: Clone + Hash> Hash for Vector<A>`

[src]

`impl<A: Clone + Hash> Hash for Vector<A>`

`fn hash<H: Hasher>(&self, state: &mut H)`

[src]

`fn hash<H: Hasher>(&self, state: &mut H)`

Feeds this value into the given [`Hasher`

]. Read more

`fn hash_slice<H>(data: &[Self], state: &mut H) where`

H: Hasher,

1.3.0[src]

`fn hash_slice<H>(data: &[Self], state: &mut H) where`

H: Hasher,

Feeds a slice of this type into the given [`Hasher`

]. Read more

`impl<A: Clone> Sum for Vector<A>`

[src]

`impl<A: Clone> Sum for Vector<A>`

`fn sum<I>(it: I) -> Self where`

I: Iterator<Item = Self>,

[src]

`fn sum<I>(it: I) -> Self where`

I: Iterator<Item = Self>,

Method which takes an iterator and generates `Self`

from the elements by "summing up" the items. Read more

`impl<A: Clone> Add for Vector<A>`

[src]

`impl<A: Clone> Add for Vector<A>`

`type Output = Vector<A>`

The resulting type after applying the `+`

operator.

`fn add(self, other: Self) -> Self::Output`

[src]

`fn add(self, other: Self) -> Self::Output`

Concatenate two vectors.

Time: O(log n)

`impl<'a, A: Clone> Add for &'a Vector<A>`

[src]

`impl<'a, A: Clone> Add for &'a Vector<A>`

`type Output = Vector<A>`

The resulting type after applying the `+`

operator.

`fn add(self, other: Self) -> Self::Output`

[src]

`fn add(self, other: Self) -> Self::Output`

Concatenate two vectors.

Time: O(log n)

`impl<A: Clone> Extend<A> for Vector<A>`

[src]

`impl<A: Clone> Extend<A> for Vector<A>`

`fn extend<I>(&mut self, iter: I) where`

I: IntoIterator<Item = A>,

[src]

`fn extend<I>(&mut self, iter: I) where`

I: IntoIterator<Item = A>,

Add values to the end of a vector by consuming an iterator.

Time: O(n)

`impl<A: Clone> Index<usize> for Vector<A>`

[src]

`impl<A: Clone> Index<usize> for Vector<A>`

`type Output = A`

The returned type after indexing.

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

[src]

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

Get a reference to the value at index `index`

in the vector.

Time: O(log n)

`impl<A: Clone> IndexMut<usize> for Vector<A>`

[src]

`impl<A: Clone> IndexMut<usize> for Vector<A>`

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

[src]

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

Get a mutable reference to the value at index `index`

in the
vector.

Time: O(log n)

`impl<'a, A: Clone> IntoIterator for &'a Vector<A>`

[src]

`impl<'a, A: Clone> IntoIterator for &'a Vector<A>`

`type Item = &'a A`

The type of the elements being iterated over.

`type IntoIter = Iter<'a, A>`

Which kind of iterator are we turning this into?

`fn into_iter(self) -> Self::IntoIter`

[src]

`fn into_iter(self) -> Self::IntoIter`

Creates an iterator from a value. Read more

`impl<A: Clone> IntoIterator for Vector<A>`

[src]

`impl<A: Clone> IntoIterator for Vector<A>`

`type Item = A`

The type of the elements being iterated over.

`type IntoIter = ConsumingIter<A>`

Which kind of iterator are we turning this into?

`fn into_iter(self) -> Self::IntoIter`

[src]

`fn into_iter(self) -> Self::IntoIter`

Creates an iterator from a value. Read more

`impl<A: Clone> FromIterator<A> for Vector<A>`

[src]

`impl<A: Clone> FromIterator<A> for Vector<A>`

`fn from_iter<I>(iter: I) -> Self where`

I: IntoIterator<Item = A>,

[src]

`fn from_iter<I>(iter: I) -> Self where`

I: IntoIterator<Item = A>,

Create a vector from an iterator.

Time: O(n)

`impl<'s, 'a, A, OA> From<&'s Vector<&'a A>> for Vector<OA> where`

A: ToOwned<Owned = OA>,

OA: Borrow<A> + Clone,

[src]

`impl<'s, 'a, A, OA> From<&'s Vector<&'a A>> for Vector<OA> where`

A: ToOwned<Owned = OA>,

OA: Borrow<A> + Clone,

`impl<'a, A: Clone> From<&'a [A]> for Vector<A>`

[src]

`impl<'a, A: Clone> From<&'a [A]> for Vector<A>`

`impl<A: Clone> From<Vec<A>> for Vector<A>`

[src]

`impl<A: Clone> From<Vec<A>> for Vector<A>`

`fn from(vec: Vec<A>) -> Self`

[src]

`fn from(vec: Vec<A>) -> Self`

Create a vector from a `std::vec::Vec`

.

Time: O(n)

`impl<'a, A: Clone> From<&'a Vec<A>> for Vector<A>`

[src]

`impl<'a, A: Clone> From<&'a Vec<A>> for Vector<A>`

`fn from(vec: &Vec<A>) -> Self`

[src]

`fn from(vec: &Vec<A>) -> Self`

Create a vector from a `std::vec::Vec`

.

Time: O(n)