Struct ConsolidatingVec

pub(crate) struct ConsolidatingVec<D> {
    data: Vec<(D, Diff)>,
    min_capacity: usize,
    growth_dampener: usize,
}

A vector that consolidates its contents.

The vector is filled with updates until it reaches capacity. At this point, the updates are consolidated to free up space. This process repeats until the consolidation recovered less than half of the vector’s capacity, at which point the capacity is doubled.

Fields

data: Vec<(D, Diff)>

min_capacity: usize

A lower bound for how small we’ll shrink the Vec’s capacity. NB: The cap might start smaller than this.

growth_dampener: usize

Dampener in the growth rate. 0 corresponds to doubling and in general n to 1+1/(n+1).

If consolidation didn’t free enough space, at least a linear amount, increase the capacity Setting this to 0 results in doubling whenever the list is at least half full. Larger numbers result in more conservative approaches that use more CPU, but less memory.

Implementations

impl<D: Ord> ConsolidatingVec<D>

pub fn new(min_capacity: usize, growth_dampener: usize) -> Self

Creates a new instance from the necessary configuration arguments.

pub fn len(&self) -> usize

Return the length of the vector.

pub fn capacity(&self) -> usize

Return the capacity of the vector.

pub fn push(&mut self, item: (D, Diff))

Pushes item into the vector.

If the vector does not have sufficient capacity, we’ll first consolidate and then increase its capacity if the consolidated results still occupy a significant fraction of the vector.

The worst-case cost of this function is O(n log n) in the number of items the vector stores, but amortizes to O(log n).

pub fn consolidate(&mut self)

Consolidate the contents.

pub fn iter(&self) -> impl Iterator<Item = &(D, Diff)>

Return an iterator over the borrowed items.

pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut (D, Diff)>

Returns mutable access to the underlying items.

Trait Implementations

impl<D: Debug> Debug for ConsolidatingVec<D>

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

Formats the value using the given formatter.

impl<D: Ord> Extend<(D, Overflowing<i64>)> for ConsolidatingVec<D>

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

where I: IntoIterator<Item = (D, Diff)>,

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<D> FromIterator<(D, Overflowing<i64>)> for ConsolidatingVec<D>

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

where I: IntoIterator<Item = (D, Diff)>,

Creates a value from an iterator.

impl<D> IntoIterator for ConsolidatingVec<D>

type Item = (D, Overflowing<i64>)

The type of the elements being iterated over.

type IntoIter = IntoIter<(D, Overflowing<i64>)>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.