Crate segvec

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:

Pros:

• 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.

Cons:

• 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

Use Cases

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

Features

• 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

• detail

Structs

• 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.

Traits

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