unsafe Rust free!
A vector-like data structure that organizes its elements into a set of buckets of fixed-capacity in order to guarantee that mutations to the bucket vector never moves elements and thus invalidates references to them.
This is comparable to a
Vec<Box<T>> but a lot more efficient.
BucketVec is really just a vector of
Whenever an element is pushed to the
BucketVec the element is pushed onto
Bucket if it isn't filled, yet.
If the last
Bucket is filled a new
Bucket is pushed onto the
with a new capacity determined by the used bucket vector configuration.
This way the
BucketVec never moves elements around upon inserting new elements
in order to preserve references. When a normal
Vec is modified it can potentially
invalidate references because of reallocation of the internal buffer which
might cause severe bugs if references to the internal elements are stored
Vec. Note that normally Rust prevents such situations so the
BucketVec is mainly used in the area of
unsafe Rust where a developer
actively decides that they want or need pinned references into another data
For the same reasons as stated above the
BucketVec does not allow to remove
or swap elements.
Looking at an example
BucketVec<i32> with the following configuration:
start_capacity := 1
growth_rate := 2
We have already pushed the elements
K onto it.
[ [A], [B, C], [D, E, F, G], [H, I, J, K, _, _, _, _] ]
_ refers to a vacant bucket entry.
O onto the same
BucketVec results in:
[ [A], [B, C], [D, E, F, G], [H, I, J, K, L, M, N, O] ]
So we are full on capacity for all buckets.
The next time we push another element onto the
BucketVec it will create a new
Bucket with a capacity of
growth_rate == 2 and our current latest bucket already has a capacity of
[ [A], [B, C], [D, E, F, G], [H, I, J, K, L, M, N, O], [P, 15 x _] ]
15 x _ denotes 15 consecutive vacant entries.
Accessor into a recently pushed element.
A vector-like data structure that never moves its contained elements.
An iterator yielding the elements of a bucket vector by value.
An iterator yielding shared references to the elements of a bucket vector.
An iterator yielding exclusive references to the elements of a bucket vector.
The default configuration for bucket vectors.
Basic configs of a bucket vector.