Crate extarray 

An implemenation of extensible arrays as described in section 3 of the paper “Immediate-Access Indexing Using Space-Efficient Extensible Arrays” by Alistair Moffat and Joel Mackenzie, published in 2022.

• ACM ISBN 979-8-4007-0021-7/22/12
• https://doi.org/10.1145/3572960.3572984

Memory Usage

An empty resizable array is approximately 88 bytes in size, and while holding elements it will have a space overhead on the order of O(√N). 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

Most operations are either constant time, log2, or sqrt of the collection size. However, the lookup operation involves several calculations and as such the overall performance will be worse than Vec. The advantage is that the memory overhead will be on the order of O(√N) vs O(N).

Safety

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

Structs

ExtArrayIntoIter

An iterator that moves out of a extensible array.

ExtArrayIter

Immutable extensible array iterator.

ExtensibleArray

Growable array as described by Moffat and Mackenzie.