STL: vector vs. list

They solve different problems, so it depends on the "shape" of your data, and which is more important to you, inserting, deleting or accessing quickly.

Lists are double-linked lists, so insertion at either end, or in the middle (providing you know an existing element in the middle) is equally fast. Also, splicing is fast (eg. putting a list into the middle of another) - all that does is re-arrange the end pointers. All of those operations would be slower with vectors, because you would need to copy everything.

eg. Inserting into the middle of a vector of 1000 items would involve moving 500 items up one. Similarly with deleting. In fact, vectors are really only good for insertion and deletion at the end.

For things that require insertion and deletion, but only at *each* end (like a queue) then there is a dequeue (double-ended queue) which is really a collection of vectors. This is more efficient.

However, vectors shine in random access - since they are organised sequentially in memory, whilst this is slow for insertion at anywhere other than the end, you can easily find, say, element 500, you simply index into the vector. Thus, vectors can be sorted, shuffled, and accessed randomly.