Struct SegmentedVec 

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

A segmented vector with stable pointers.

Implementations

impl<T> SegmentedVec<T>

pub const fn new() -> Self

Creates a new empty SegmentedVec.

Example

use segmented_vec::SegmentedVec;
let vec: SegmentedVec<i32> = SegmentedVec::new();
assert!(vec.is_empty());

pub const fn len(&self) -> usize

Returns the number of elements in the vector.

pub const fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

pub fn capacity(&self) -> usize

Returns the current capacity of the vector.

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

Appends an element to the back of the vector.

Panics

Panics if allocation fails.

Example

use segmented_vec::SegmentedVec;
let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.push(1);
vec.push(2);
assert_eq!(vec.len(), 2);

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

Removes the last element from the vector and returns it, or None if empty.

Example

use segmented_vec::SegmentedVec;
let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.push(1);
vec.push(2);
assert_eq!(vec.pop(), Some(2));
assert_eq!(vec.pop(), Some(1));
assert_eq!(vec.pop(), None);

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

Returns a reference to the element at the given index.

Returns None if the index is out of bounds.

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

Returns a mutable reference to the element at the given index.

Returns None if the index is out of bounds.

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

Returns a reference to the first element, or None if empty.

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

Returns a mutable reference to the first element, or None if empty.

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

Returns a reference to the last element, or None if empty.

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

Returns a mutable reference to the last element, or None if empty.

pub fn contains(&self, x: &T) -> bool

where T: PartialEq,

Returns true if the slice contains an element with the given value.

pub fn starts_with(&self, needle: &[T]) -> bool

where T: PartialEq,

Returns true if needle is a prefix of the vector.

pub fn ends_with(&self, needle: &[T]) -> bool

where T: PartialEq,

Returns true if needle is a suffix of the vector.

pub fn binary_search(&self, x: &T) -> Result<usize, usize>

where T: Ord,

Binary searches this vector for a given element.

If the value is found, returns Ok(index). If not found, returns Err(index) where index is the position where the element could be inserted.

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

where F: FnMut(&T) -> Ordering,

Binary searches this vector with a comparator function.

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

where F: FnMut(&T) -> B, B: Ord,

Binary searches this vector with a key extraction function.

pub fn swap(&mut self, a: usize, b: usize)

Swaps two elements in the vector.

Panics

Panics if a or b are out of bounds.

pub fn reverse(&mut self)

Reverses the order of elements in the vector.

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

where T: Clone,

Fills the vector with the given value.

pub fn fill_with<F>(&mut self, f: F)

where F: FnMut() -> T,

Fills the vector with values produced by a function.

pub fn clear(&mut self)

Clears the vector, removing all elements.

This does not deallocate the dynamic segments.

pub fn truncate(&mut self, new_len: usize)

Shortens the vector, keeping the first new_len elements.

If new_len is greater than or equal to the current length, this has no effect.

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements.

pub fn shrink_to_fit(&mut self)

Shrinks the capacity to match the current length.

This deallocates unused dynamic segments.

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

Returns an iterator over references to the elements.

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

Returns an iterator over mutable references to the elements.

pub fn as_slice(&self) -> SegmentedSlice<'_, T>

Returns an immutable slice view of the entire vector.

Example

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend(0..10);

let slice = vec.as_slice();
assert_eq!(slice.len(), 10);
assert_eq!(slice[0], 0);

pub fn as_mut_slice(&mut self) -> SegmentedSliceMut<'_, T>

Returns a mutable slice view of the entire vector.

Example

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend(0..10);

let mut slice = vec.as_mut_slice();
slice[0] = 100;
assert_eq!(vec[0], 100);

pub fn slice(&self, range: Range<usize>) -> SegmentedSlice<'_, T>

Returns an immutable slice view of a range of the vector.

Panics

Panics if the range is out of bounds.

Example

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend(0..10);

let slice = vec.slice(2..5);
assert_eq!(slice.len(), 3);
assert_eq!(slice[0], 2);

pub fn slice_mut(&mut self, range: Range<usize>) -> SegmentedSliceMut<'_, T>

Returns a mutable slice view of a range of the vector.

Panics

Panics if the range is out of bounds.

Example

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend(0..10);

let mut slice = vec.slice_mut(2..5);
slice[0] = 100;
assert_eq!(vec[2], 100);

pub fn extend_from_slice(&mut self, other: &[T])

where T: Clone,

Extends the vector by cloning elements from a slice.

pub fn extend_from_copy_slice(&mut self, other: &[T])

where T: Copy,

Extends the vector by copying elements from a slice (for Copy types).

This is more efficient than extend_from_slice for Copy types as it uses bulk memory copy operations.

pub fn sort(&mut self)

where T: Ord,

Sorts the vector in place using a stable sorting algorithm.

This sort is stable (i.e., does not reorder equal elements) and O(n * log(n)) worst-case.

The algorithm is a merge sort adapted from the Rust standard library.

Examples

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend([3, 1, 4, 1, 5, 9, 2, 6]);
vec.sort();
assert_eq!(vec.iter().copied().collect::<Vec<_>>(), vec![1, 1, 2, 3, 4, 5, 6, 9]);

pub fn sort_by<F>(&mut self, compare: F)

where F: FnMut(&T, &T) -> Ordering,

Sorts the vector in place with a comparator function.

This sort is stable (i.e., does not reorder equal elements) and O(n * log(n)) worst-case.

The comparator function must define a total ordering for the elements.

Examples

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend([3, 1, 4, 1, 5, 9, 2, 6]);
vec.sort_by(|a, b| b.cmp(a)); // reverse order
assert_eq!(vec.iter().copied().collect::<Vec<_>>(), vec![9, 6, 5, 4, 3, 2, 1, 1]);

pub fn sort_by_key<K, F>(&mut self, f: F)

where F: FnMut(&T) -> K, K: Ord,

Sorts the vector in place with a key extraction function.

This sort is stable (i.e., does not reorder equal elements) and O(m * n * log(n)) worst-case, where the key function is O(m).

Examples

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend([-3, 1, -4, 1, 5, -9, 2, 6]);
vec.sort_by_key(|k| k.abs());
assert_eq!(vec.iter().copied().collect::<Vec<_>>(), vec![1, 1, 2, -3, -4, 5, 6, -9]);

pub fn sort_unstable(&mut self)

where T: Ord,

Sorts the vector in place using an unstable sorting algorithm.

This sort is unstable (i.e., may reorder equal elements), in-place, and O(n * log(n)) worst-case.

The algorithm is a quicksort with heapsort fallback, adapted from the Rust standard library.

Examples

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend([3, 1, 4, 1, 5, 9, 2, 6]);
vec.sort_unstable();
assert_eq!(vec.iter().copied().collect::<Vec<_>>(), vec![1, 1, 2, 3, 4, 5, 6, 9]);

pub fn sort_unstable_by<F>(&mut self, compare: F)

where F: FnMut(&T, &T) -> Ordering,

Sorts the vector in place with a comparator function using an unstable sorting algorithm.

This sort is unstable (i.e., may reorder equal elements), in-place, and O(n * log(n)) worst-case.

The comparator function must define a total ordering for the elements.

Examples

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend([3, 1, 4, 1, 5, 9, 2, 6]);
vec.sort_unstable_by(|a, b| b.cmp(a)); // reverse order
assert_eq!(vec.iter().copied().collect::<Vec<_>>(), vec![9, 6, 5, 4, 3, 2, 1, 1]);

pub fn sort_unstable_by_key<K, F>(&mut self, f: F)

where F: FnMut(&T) -> K, K: Ord,

Sorts the vector in place with a key extraction function using an unstable sorting algorithm.

This sort is unstable (i.e., may reorder equal elements), in-place, and O(n * log(n)) worst-case, where the key function is O(m).

Examples

use segmented_vec::SegmentedVec;

let mut vec: SegmentedVec<i32> = SegmentedVec::new();
vec.extend([-3, 1, -4, 1, 5, -9, 2, 6]);
vec.sort_unstable_by_key(|k| k.abs());
// Note: unstable sort may reorder equal elements, so we just check it's sorted by abs value
let result: Vec<i32> = vec.iter().copied().collect();
for i in 1..result.len() {
    assert!(result[i-1].abs() <= result[i].abs());
}

pub fn is_sorted(&self) -> bool

where T: PartialOrd,

Checks if the elements of this vector are sorted.

pub fn is_sorted_by<F>(&self, compare: F) -> bool

where F: FnMut(&T, &T) -> bool,

Checks if the elements of this vector are sorted using the given comparator function.

pub fn is_sorted_by_key<K, F>(&self, f: F) -> bool

where F: FnMut(&T) -> K, K: PartialOrd,

Checks if the elements of this vector are sorted using the given key extraction function.

pub fn partition_point<P>(&self, pred: P) -> usize

where P: FnMut(&T) -> bool,

Returns the index of the partition point according to the given predicate.

pub fn rotate_left(&mut self, mid: usize)

Rotates the vector in-place such that the first mid elements move to the end.

pub fn rotate_right(&mut self, k: usize)

Rotates the vector in-place such that the last k elements move to the front.

pub fn with_capacity(capacity: usize) -> Self

Creates a new SegmentedVec with at least the specified capacity.

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

Inserts an element at position index, shifting all elements after it to the right.

Panics

Panics if index > len.

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

Removes and returns the element at position index, shifting all elements after it to the left.

Panics

Panics if index >= len.

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, but is O(1).

Panics

Panics if index >= len.

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

where F: FnMut(&T) -> bool,

Retains only the elements specified by the predicate.

Removes all elements for which f(&element) returns false.

pub fn retain_mut<F>(&mut self, f: F)

where F: FnMut(&mut T) -> bool,

Retains only the elements specified by the predicate, passing a mutable reference.

pub fn dedup(&mut self)

where T: PartialEq,

Removes consecutive duplicate elements.

If the vector is sorted, this removes all duplicates.

pub fn dedup_by<F>(&mut self, same_bucket: F)

where F: FnMut(&mut T, &mut T) -> bool,

Removes consecutive elements that satisfy the given equality relation.

pub fn dedup_by_key<K, F>(&mut self, key: F)

where F: FnMut(&mut T) -> K, K: PartialEq,

Removes consecutive elements that map to the same key.

pub fn resize(&mut self, new_len: usize, value: T)

where T: Clone,

Resizes the vector in-place so that len is equal to new_len.

If new_len is greater than len, the vector is extended by the difference, with each additional slot filled with value. If new_len is less than len, the vector is simply truncated.

pub fn resize_with<F>(&mut self, new_len: usize, f: F)

where F: FnMut() -> T,

Resizes the vector in-place so that len is equal to new_len.

If new_len is greater than len, the vector is extended by the difference, with each additional slot filled with the result of calling the closure f.

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

Moves all the elements of other into self, leaving other empty.

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

Splits the vector into two at the given index.

Returns a newly allocated vector containing the elements in the range [at, len). After the call, the original vector will contain elements [0, at).

Panics

Panics if at > len.

pub fn chunks(&self, chunk_size: usize) -> Chunks<'_, T>

Returns an iterator over chunk_size elements of the vector at a time.

Panics

Panics if chunk_size is 0.

pub fn windows(&self, size: usize) -> Windows<'_, T>

Returns an iterator over all contiguous windows of length size.

Panics

Panics if size is 0.

pub fn rchunks(&self, chunk_size: usize) -> RChunks<'_, T>

Returns an iterator over chunk_size elements at a time, starting from the end.

Panics

Panics if chunk_size is 0.

pub fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T>

Returns an iterator over exactly chunk_size elements at a time.

Panics

Panics if chunk_size is 0.

pub fn drain(&mut self, range: Range<usize>) -> Drain<'_, T>

Creates a draining iterator that removes the specified range and yields the removed items.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length.

pub fn to_vec(&self) -> Vec<T>

where T: Clone,

Copies the elements to a new Vec<T>.

Trait Implementations

impl<T: Clone> Clone for SegmentedVec<T>

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> Debug for SegmentedVec<T>

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

Formats the value using the given formatter.

impl<T> Default for SegmentedVec<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Drop for SegmentedVec<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> Extend<T> for SegmentedVec<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T> FromIterator<T> for SegmentedVec<T>

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

Creates a value from an iterator.

impl<T> Index<usize> for SegmentedVec<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 SegmentedVec<T>

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

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

impl<'a, T> IntoIterator for &'a SegmentedVec<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut SegmentedVec<T>

type Item = &'a mut T

The type of the elements being iterated over.

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for SegmentedVec<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for SegmentedVec<T>

fn eq(&self, other: &Self) -> 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: Eq> Eq for SegmentedVec<T>