Abstract
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 set from the standard library on
sequences with up to 108 elements. Our fastest implementation uses much less space than set
while providing speedups of 40× for access operations compared to set and speedups of 10.000×
compared to vector for insertion and deletion operations while being competitive with both data
structures for all other operations.
Original language | English |
---|---|
Title of host publication | Proceedings of 5th Annual European Symposium on Algorithms |
Publication date | 2017 |
Pages | 16:1--16:13 |
ISBN (Print) | 978-3-95977-049-1 |
DOIs | |
Publication status | Published - 2017 |
Event | 25th European Symposium on Algorithms (ESA 2017) - Vienna, Austria Duration: 4 Sept 2017 → 6 Sept 2017 |
Conference
Conference | 25th European Symposium on Algorithms (ESA 2017) |
---|---|
Country/Territory | Austria |
City | Vienna |
Period | 04/09/2017 → 06/09/2017 |
Keywords
- Dynamic Arrays
- Tiered Vectors