Struct segvec::SegVec

pub struct SegVec<T> { /* fields omitted */ }

A data structure similar to Vec, but that does not copy on re-size and can release memory when it is truncated.

• Capacity is allocated in “segments”.
• For a SegVec with one element, a segment of length 1 is allocated.
• For a SegVec with 2 elements, two segments of length 1 are allocated.
• For a SegVec with 3 or 4 elements, two segments of length one, and a segment of length 2 are allocated.
• Each allocated segment is the size of the entire capacity prior to the allocation of that segment. In other words, each segment allocated doubles the capacity of the SegVec. As a consequence, a SegVec always has a capacity that is a power of 2, with the special case of the empty SegVec with a capacity of 0.

Implementations

impl<T> SegVec<T>

pub fn new() -> Self

Create a new SegVec with a length and capacity of 0

let v: SegVec<i32> = SegVec::new();
assert_eq!(v.capacity(), 0);

pub fn with_capacity(hint: usize) -> Self

Create a new SegVec with a length of 0 and a capacity large enough to hold the given number of elements.

let v: SegVec<i32> = SegVec::with_capacity(5);
assert_eq!(v.capacity(), 8);

Panics

• If the required capacity overflows usize

pub fn len(&self) -> usize

The number of elements in the SegVec

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
assert_eq!(v.len(), 2);

pub fn capacity(&self) -> usize

The capacity of the SegVec

let mut v: SegVec<i32> = SegVec::with_capacity(3);
assert_eq!(v.capacity(), 4);

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

Reserve enough capacity to insert the given number of elements into the SegVec without allocating. If the capacity is already sufficient, nothing happens.

let mut v: SegVec<i32> = SegVec::new();
assert_eq!(v.capacity(), 0);
v.reserve(3);
assert_eq!(v.capacity(), 4);

Panics

• If the required capacity overflows usize

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

Returns a reference to the data at the given index in the SegVec, if it exists.

let mut v: SegVec<i32> = SegVec::new();
assert_eq!(v.get(0), None);
v.push(1);
assert_eq!(*v.get(0).unwrap(), 1);

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

Returns a mutable reference to the data at the given index in the SegVec, if it exists.

let mut v: SegVec<i32> = SegVec::new();
assert_eq!(v.get_mut(0), None);
v.push(1);
assert_eq!(*v.get_mut(0).unwrap(), 1);

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

Pushes a new value onto the end of the SegVec, resizing if necessary.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
assert_eq!(v[0], 1);

Panics

• If the required capacity overflows usize

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

Removes the last value from the SegVec and returns it, or returns None if it is empty.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
assert_eq!(v[0], 1);

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

Truncates the SegVec to the given length. If the given length is larger than the current length, this is a no-op. Otherwise, the capacity is reduced and any excess elements are dropped.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
v.push(3);
assert_eq!(v.len(), 3);
assert_eq!(v.capacity(), 4);
v.truncate(1);
assert_eq!(v.len(), 1);
assert_eq!(v.capacity(), 1);

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

Returns an iterator over immutable references to the elements in the SegVec.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
v.push(3);
let mut i = v.iter();
assert_eq!(*i.next().unwrap(), 1);
assert_eq!(*i.next().unwrap(), 2);
assert_eq!(*i.next().unwrap(), 3);
assert_eq!(i.next(), None);

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

Insert the given value at the given index in the SegVec. This operation requires O(N) time due to the fact that the data is segmented - the new element is pushed onto the end and then shifted backwards into position.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
v.insert(0, 100);
assert_eq!(v[0], 100);

Panics

• If the given index is greater than self.len()
• If the required capacity overflows usize

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

Removes the value at the given index in the SegVec and returns it. This operation requires O(N) time due to the fact that the data is segmented - the element is shifted to the end and then popped.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
assert_eq!(v.remove(1), 2);
assert_eq!(v.len(), 1);

Panics

• If the given index is greater than or equal to self.len()

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

Returns an iterator that removes and returns values from within the given range of the SegVec. See Drain for more information.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
v.drain(..).for_each(|v| println!("{}", v));
assert_eq!(v.len(), 0);

Panics

• If the end index is greater than self.len()
• If the start index is greater than the end index.

pub fn slice<R>(&self, range: R) -> Slice<'_, T> where
    R: RangeBounds<usize>, 

Returns a Slice over the given range in the SegVec.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
let s = v.slice(1..);
assert_eq!(s[0], 2);

Panics

• If the end index is greater than self.len()
• If the start index is greater than the end index.

pub fn slice_mut<R>(&mut self, range: R) -> SliceMut<'_, T> where
    R: RangeBounds<usize>, 

Returns a SliceMut over the given range in the SegVec.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
let mut s = v.slice_mut(..1);
s[0] = 100;
assert_eq!(v[0], 100);

Panics

• If the end index is greater than self.len()
• If the start index is greater than the end index.

pub fn reverse(&mut self)

Reverses the elements in the SegVec.

let mut v: SegVec<i32> = SegVec::new();
v.push(1);
v.push(2);
v.push(3);
v.push(4);
v.push(5);
v.push(6);
v.reverse();
assert_eq!(v.into_iter().collect::<Vec<_>>(), vec![6, 5, 4, 3, 2, 1]);

pub fn sort_unstable(&mut self) where
    T: Ord, 

Sort the SegVec in ascending order (unstable)

pub fn sort_unstable_by<F>(&mut self, compare: F) where
    F: FnMut(&T, &T) -> Ordering, 

Sort the SegVec in ascending order (unstable) using the given comparison function

Trait Implementations

impl<T: Clone> Clone for SegVec<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for SegVec<T>

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

Formats the value using the given formatter.

impl<T> Extend<T> for SegVec<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 SegVec<T>

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

Creates a value from an iterator.

impl<T: Hash> Hash for SegVec<T>

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

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

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

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

impl<T> IntoIterator for SegVec<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> PartialEq<SegVec<T>> for SegVec<T> where
    T: PartialEq, 

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl<T> Eq for SegVec<T> where
    T: Eq,