File ArraySequence.h

↰ Parent directory (ADS/sequence)

A SEQUENCE [see File ADT.h] realized with a vector: the position of an item is its index, :math:` pos_i = i , with :math: pos_{-1} = -1 ` and :math:` pos_n = n `.

Definition (ADS/sequence/ArraySequence.h)

Detailed Description

Moving along the sequence, reading and writing take O( 1 ) time, while insert() and remove() take O( n ) time, since the items after the position move by one place; inserting at the end takes O( 1 ) amortized time, since a full vector is replaced by one of twice its size. If the i-th insertion costs :math:` c_i = i ` when it finds the vector full, i.e., when :math:` i = 2^k + 1 `, and 1 otherwise, then n insertions cost :math:`[
C( n ) = sum_{i=1}^n c_i leq n + sum_{k=0}^{lfloor log_2 n rfloor}

2^k leq n + 2^{lfloor log_2 n rfloor + 1} - 1 leq 3 n ; ,

` whereas growing the vector by a constant d makes them cost :math:` Theta( n^2 ) . Symmetrically, a vector that remove() leaves with :math: n leq capacity / 4 ` is replaced by one of half its size, so that the space stays O( n ) and any sequence of insertions and removals costs O( 1 ) amortized time each: after a resize the vector is half full, and :math:` Omega( capacity ) ` operations must come before the next one. The empty sequence has no vector, also when remove() empties it, the first insertion makes one of one place, and moving a sequence takes its vector in O( 1 ) time, leaving the one moved from empty.

The contracts [see File Contract.h]: a position is an index from -1 to n; next() needs one from -1 to n - 1 and prev() one from 0 to n, since there is nothing after :math:` pos_n ` nor before :math:` pos_{-1} ; insert() needs one from 0 to n, and read(), write() and remove() one that holds an item, from 0 to n - 1. insert() and write() ensure that v is read back in its place, and that the other items are where they were (or one place on, after the insertion), the latter costing O( n ) and therefore an audit; remove() likewise. The invariant is that the n items fit in the vector, :math: 0 leq n leq capacity `. The operations are defined in ArraySequence.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 4.2, 4.2.1 and 4.5, https://algoritmicamente.it/materiali/libro/capitoli/cap04.pdf

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, section 17.4 (dynamic tables, the contraction at a quarter)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes