Vector Hosted Lists--Thomas Young
Want perfomance and speed? Vectors are the solution:
Vector Hosted Lists
by Thomas Young
From the article:
Vectors are great when adding or removing elements at the end of a sequence, but not so hot when deleting elements at arbitrary positions.
If that's a requirement, you might find yourself reaching for a pointer-based list.
Not so fast!
Memory locality is important, contiguous buffers are a really good thing, and a standard vector will often out-perform pointer-based lists even where you perform non-contiguous, list-style modifications such as arbitrary element deletion.
And we can 'host' a list within a vector to get the advantages of a contiguous buffer at the same time as 0(1) complexity for these kinds of manipulations...