Crate extarray 

An append-only (no insert or remove) growable array 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

This data structure is meant to hold an unknown, though likely large, number of elements, otherwise Vec would be more appropriate. An empty array will have a size of around 40 bytes. The size may not be an issue, but the lookup operation has a non-trivial cost, unlike Vec.

Performance

Most operations are either constant time, or 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 difference will be in how memory is allocated over time, which should help with arena memory allocators.

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

Append-only growable array that uses a list of progressivly larger segments to avoid the allocate-and-copy that many growable data structures typically employ.