Crate segvec

Expand description

This crate provides the SegVec data structure.

It is similar to Vec, but allocates memory in chunks, referred to as “segments”. This involves a few trade-offs:

Element addresses are stable across push operations even if the SegVec must grow.
Resizing only allocates the additional space needed, and doesn’t require copying.

Operations are slower (some, like insert, remove, and drain, are much slower) than for a Vec due to the need for multiple pointer dereferences and conversion between linear indexes and (segment, offset) pairs
Direct slicing is unavailable (i.e. no &[T] or &mut [T]), though slice and slice_mut are available

You have a long-lived Vec whose size fluctuates between very large and very small throughout the life of the program.
You have a large append-only Vec and would benefit from stable references to the elements

small-vec - Uses SmallVec instead of Vec to store the list of segments, allowing the first few segment headers to live on the stack. Can speed up access for small SegVec values.
thin-segments - Uses ThinVec instead of Vec to store the data for each segment, meaning that each segment header takes up the space of a single usize, rathern than 3 when using Vec.

Modules§

Drain: Removes and returns elements from a range in a SegVec. Any un-consumed elements are removed and dropped when a Drain is dropped. If a Drain is forgotten (via std::mem::forget), it is unspecified how many elements are removed. The current implementation calls SegVec::remove on a single element on each call to next.
Exponential: Exponential growth, each subsequent segment is as big as the sum of all segments before.
IntoIter: Consuming iterator over items in a SegVec.
Iter: Iterator over immutable references to items in a SegVec.
Linear: Linear growth, all segments have the same (FACTOR) length.
Proportional: Proportional growth, each segment is segment_number*FACTOR sized.
SegVec: A data structure similar to Vec, but that does not copy on re-size and can release memory when it is truncated.
SegmentedIter: Iterator over immutable references to slices of the elements of a Slice.
SegmentedMutIter: Iterator over mutable references to slices of the elements of a SliceMut.
Slice: Provides an immutable view of elements from a range in SegVec.
SliceIter: Iterator over immutable references to the elements of a Slice.
SliceMut: Provides a mutable view of elements from a range in SegVec.
SliceMutIter: Iterator over immutable references to the elements of a SliceMut.

MemConfig: Configures the sizes of segments and how to index entries. Linear, Proportional and Exponential implement this trait.