Expand description
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 theSegVec
must grow. - Resizing only allocates the additional space needed, and doesn’t require copying.
Cons:
- Operations are slower (some, like
insert
,remove
, anddrain
, are much slower) than for aVec
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]
), thoughslice
andslice_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
- UsesSmallVec
instead ofVec
to store the list of segments, allowing the first few segment headers to live on the stack. Can speed up access for smallSegVec
values.thin-segments
- UsesThinVec
instead ofVec
to store the data for each segment, meaning that each segment header takes up the space of a singleusize
, rathern than 3 when usingVec
.
Structs
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
.
A data structure similar to Vec
, but that does not copy on re-size and can
release memory when it is truncated.
Iterator over mutable references to the elements of a SliceMut
.