Struct segvec::SegVec

pub struct SegVec<T, C: MemConfig = Exponential<1>> { /* private fields */ }

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”. A empty SegVec of capacity 0 does not allocate. Allocating new segments is controlled by a MemConfig policy. Segvec comes with three predefined implementations. These implementations take an non-zero parameter which defines the minimum number of elements in a segment, all segments are multiples of this ‘FACTOR’. This FACTOR should ideally be a power of two as this optimizes to much more efficient code.

1. Linear<FACTOR> All segments have the same size. This is the fastest when FACTOR is big enough. Consequently there is some memory overhead when only very few elements are stored. When a SegVec grows it will have the least memory overhead. When not given then FACTOR defaults to 1024.
2. Proportional<FACTOR> Segments grow proportionally to their segment number [FACTOR, 2*FACTOR, 3*FACTOR, ..]. Unfortunately the math is somewhat expensive which makes this slow.
3. Exponential<FACTOR> Segments grow exponentially to their segment number, each subsequent segment is as large as the size of all preceeding segments [FACTOR, FACTOR, 2*FACTOR, 4*FACTOR, 8*FACTOR, ..]. Exponential is slightly wasteful with memory (up to 50% might be unused in the worst case). When not given then FACTOR defaults to 16.

The default MemConfig is Exponential<1> which should work for most cases, especially when very few elements are frequently expected.

Altogether you get these three defaults:

• SegVec<T> Use it when very few elements (less than 10) are frequently expected.
• SegVec<T, Exponential> Good compromise when the expected number of elements can vary widely.
• SegVec<T, Linear> The fastest. But wastes memory when only few elements are expected (<500).

Implementations

impl<T, C: MemConfig> SegVec<T, C>

pub fn new() -> Self

Create a new SegVec with a length and capacity of 0.

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

pub fn with_capacity(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!(v.capacity() >= 5);

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 is_empty(&self) -> bool

Returns true if the SegVec contains no elements.

let mut v: SegVec<i32> = SegVec::with_capacity(10);
assert!(v.is_empty());
v.push(1);
assert!(!v.is_empty());

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.pop().unwrap(), 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!(v.capacity() >= 3);
v.truncate(1);
assert_eq!(v.len(), 1);

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

Resizes the SegVec so that the length is equal to new_len.

If new_len is greater than len, the SegVec is extended by the difference, with each additional slot filled with the result of calling the closure f. The return values from f will end up in the SegVec in the order they have been generated. If new_len is less than len, the SegVec is simply truncated. If new_len is equal to len, this is a no-op.

let mut v: SegVec<i32> = SegVec::new();
let mut counter = 0i32;
v.resize_with(4, || { counter += 1; counter });
assert_eq!(counter, 4);
assert_eq!(v.len(), 4);
assert_eq!(v.pop().unwrap(), 4);

pub fn resize(&mut self, new_len: usize, val: T)where T: Clone,

Resizes the SegVec so that the length is equal to new_len.

If new_len is greater than len, the SegVec is extended by the difference, with each additional slot filled with the result of calling the clone on val. The cloned values will end up in the SegVec in the order they have been generated. If new_len is less than len, the SegVec is simply truncated. If new_len is equal to len, this is a no-op.

let mut v: SegVec<i32> = SegVec::new();
v.resize(4, 100);
assert_eq!(v.len(), 4);
assert_eq!(v.pop().unwrap(), 100);

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, C> 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, C: MemConfig> Clone for SegVec<T, C>

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, C: MemConfig> Debug for SegVec<T, C>

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

Formats the value using the given formatter.

impl<T, C: MemConfig> Default for SegVec<T, C>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T: Copy + 'a, C: MemConfig> Extend<&'a T> for SegVec<T, C>

fn extend<I: IntoIterator<Item = &'a 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, C: MemConfig> Extend<T> for SegVec<T, C>

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<'a, T: Clone + 'a, C: MemConfig> FromIterator<&'a T> for SegVec<T, C>

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

Creates a value from an iterator.

impl<T, C: MemConfig> FromIterator<T> for SegVec<T, C>

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

Creates a value from an iterator.

impl<T: Hash, C: MemConfig> Hash for SegVec<T, C>

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, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T, C: MemConfig> Index<usize> for SegVec<T, C>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T, C: MemConfig> IndexMut<usize> for SegVec<T, C>

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

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

impl<T, C: MemConfig> IntoIterator for SegVec<T, C>

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, C: MemConfig> PartialEq<SegVec<T, C>> for SegVec<T, C>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 !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, C: MemConfig> Eq for SegVec<T, C>where Self: PartialEq,