File TieredVector.h

↰ Parent directory (ADS/sequence)

The tiered vector of Goodrich and Kloss, beyond the book: a sequence with access by index in O( 1 ) time, as a vector, and insertion and removal at any index in :math:` O( sqrt{n} ) ` time, where a vector [see File ArraySequence.h] moves O( n ) items.

Definition (ADS/sequence/TieredVector.h)

Detailed Description

The items are in blocks of b items, b a power of 2, each a circular buffer with the offset of its first item, all full but the last one; the item of index i is the item :math:` i bmod b ` of the block :math:` lfloor i / b rfloor , a shift, a mask and two reads. An insertion at i moves the items of its block after i by one place, at most b - 1 of them, and then the last item of each following block to the front of the next one, O( 1 ) per block since a circular buffer grows at the front by moving its offset: :math: O( b + n / b ) ` moves. A removal is the symmetric. b follows the size, the least power of 2 not below :math:` sqrt{n} ` and 64 at least: when n leaves :math:` [ b^2 / 4 , 4 b^2 ] ` the items are copied into the blocks of the new b, in O( n ) time once every :math:` Omega( n ) ` operations, so that an insertion or a removal costs :math:` O( sqrt{n} ) ` amortized and the space is :math:` n + O( sqrt{n} ) ` items.

The contracts [see File Contract.h]: an index is below size() (at most size() for an insertion), and pop_back() needs a vector that is not empty; the invariant, checked on vectors of at most 1024 items, is that the blocks but the last are full and that they count size() items. The operations are defined in TieredVector.tpp.

    1. Goodrich, J. G. Kloss II, Tiered vectors: efficient dynamic arrays for rank-based sequences, Algorithms and Data Structures (WADS 1999), Lecture Notes in Computer Science 1663, 205-216, 1999, doi:10.1007/3-540-48447-7_21

  1. Bille, A. R. Christiansen, M. B. Ettienne, I. L. Gortz, Fast dynamic arrays, 25th Annual European Symposium on Algorithms (ESA 2017), LIPIcs 87, 16:1-16:13, 2017, doi:10.4230/LIPIcs.ESA.2017.16

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes