2026-07-23T05:17:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7830 2024-03-06T10:41:16Z ddc:004 open_access

Fast Dynamic Arrays Bille, Philip Christiansen, Anders Roy Ettienne, Mikko Berggren Gørtz, Inge Li Dynamic Arrays Tiered Vectors 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^e) for e > 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 10^8 elements. Our fastest implementation uses much less space than set while providing speedups of 40x for access operations compared to set and speedups of 10.000x compared to vector for insertion and deletion operations while being competitive with both data structures for all other operations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philip Bille and Anders Roy Christiansen and Mikko Berggren Ettienne and Inge Li Gørtz 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.16 urn:nbn:de:0030-drops-78309 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.16 eng https://creativecommons.org/licenses/by/3.0/legalcode