Module simple 

The streamlined implementation of the resizable array which behaves as if the r value is fixed at 3.

This data structure does not have the additional level of indirection found in the generalized solution, and many of the operations have a constant time complexity since there are only two data block sizes, B (small) and B^2 (large). As such, the performance of this implementation is significantly better than the general version.

Memory Usage

An empty resizable array is approximately 128 bytes in size, and while holding elements it will have a space overhead on the order of O(N^1/3) as described in Section 5 of the paper. As elements are added the array will grow by allocating additional data blocks. Likewise, as elements are removed from the end of the array, data blocks will be deallocated as they become empty. At most one empty data block will be retained as an optimization.

Performance

The performance and memory usage of this data structure is complicated, please refer to the original paper for details.

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

OptArrayIntoIter

An iterator that moves out of an optimal array.

OptArrayIter

Immutable array iterator.

OptimalArray

A simplified version of the optimal resizable array for which the unused space is on the order of O(N^1/3) plus additional overhead for the data block indices.