Polymake Template Library (PTL) 4.14
Performance Comparison of Vector Classes

The following brief analysis might help you when choosing the most efficient representation for a concrete case. n is the number of (non-zero in sparse case) elements in the vector.

Performance comparison
OperationVectorSparseVector
sequential iterationO(n)O(n), but with greater overhead constant
random element accessO(1)O(log(n))
append an elementO(n) + reallocation costsO(1) if no preceding random access operations were performed on the sparse vector; O(log(n)) if there already were random access operations on the sparse vector