文章基本信息

标题：Fast Dynamic Arrays
本地全文：下载
作者：Philip Bille ; Anders Roy Christiansen ; Mikko Berggren Ettienne 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：16:1-16:13
DOI：10.4230/LIPIcs.ESA.2017.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Dynamic Arrays; Tiered Vectors