Expand description
An implementation of resizable arrays as described in the paper Resizable Arrays in Optimal Time and Space by Andrej Brodnik et. al., published in 1999.
- Online ISBN 978-3-540-48447-9
- https://doi.org/10.1137/23M1575792
§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 numerous calculations and as
such the overall performance will be worse than Vec. The difference will
be in substantially reduced memory overhead.
§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§
- OptArray
Into Iter - An iterator that moves out of an optimal array.
- OptArray
Iter - Immutable array iterator.
- Optimal
Array - Resizable array in optimal space and time (in theory).