segvec

This crate provides the SegVec data structure.

It is similar to Vec, but allocates memory in chunks of increasing size, 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) for a SegVec than for a Vec (multiple pointer dereferences, mapping indices to (segment, offset) pairs)
Direct slicing is unavailable (i.e. no &[T] or &mut [T]), though slice and slice_mut are available

Use Cases

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

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.

License: MIT