Crate tiered_vector 

An implementation of tiered vectors as described in the paper Tiered Vectors by Goodrich and Kloss II, published in 1999.

• DOI:10.1007/3-540-48447-7_21

This implementation is based on the algorithms described in the 1998 version of the paper titled Tiered Vector by the same authors. In short, the structure consists of a dope vector that references one or more circular buffers in which all buffers are full, with the exception of the last buffer which may be partially filled.

Memory Usage

An empty resizable vector is approximately 72 bytes in size, and while holding elements it will have a space overhead on the order of O(√N) as described in the paper. As elements are added the vector will grow by allocating additional data blocks. Likewise, as elements are removed from the vector, data blocks will be deallocated as they become empty.

Performance

The performance and memory layout is as described in the paper: O(√N) space overhead, O(1) get and update operations, and O(√n) insert and remove.

Safety

Because this data structure is allocating memory, copying bytes using raw pointers, and de-allocating memory as needed, there are many unsafe blocks throughout the code.

Structs

CyclicArray

Basic circular buffer, or what Goodrich and Kloss call a circular deque.

Vector

Tiered vector which maintains a collection of circular deques in order to efficiently support insert and remove from any location within the vector.

VectorIntoIter

An iterator that moves out of a tiered vector.

VectorIter

Immutable array iterator.