Comment Comment by meuk This is cool. I wanted to comment on the necessity of knowing the approximate size of N a priori, but this is very clearly stated on the github page.Interesting alternatives that also support insertion, deletion, and lookup (is there a name for this interface?) are AVL trees and hash tables.As described in https://arxiv.org/pdf/1711.00275.pdf, tiered vectors can be improved further:"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." parent meuk 7 years ago
Interesting alternatives that also support insertion, deletion, and lookup (is there a name for this interface?) are AVL trees and hash tables.
As described in https://arxiv.org/pdf/1711.00275.pdf, tiered vectors can be improved further:
"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."