Fast Dynamic Arrays

11/01/2017
by   Philip Bille, et al.
0

We present a highly optimized implementation of tiered vectors, a data structure for maintaining a sequence of n elements supporting access in time O(1) and insertion and deletion in time O(n^ϵ) for ϵ > 0 while using o(n) extra space. We consider several different implementation optimizations in C++ and compare their performance to that of vector and multiset from the standard library on sequences with up to 10^8 elements. Our fastest implementation uses much less space than multiset while providing speedups of 40× for access operations compared to multiset and speedups of 10.000× compared to vector for insertion and deletion operations while being competitive with both data structures for all other operations.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset