When do you prefer using std::list<T> instead of std::vector<T>?

So my question is: when exactly do you prefer std::list over std::vector?

When I need a sequential container in a performance-sensitive area and profiling shows std::list is faster.

So far, this has never happened to me.

(I might be tempted to try std::list first when I would have to store very big objects with lots of insertion/removal in the middle. However, in practice, I've never come across such a use-case.)

Lists are better for inserting or deleting anywhere in the middle, vectors are better for inserting at the end.

Vectors are also better for accessing elements.

This is an artefact of the way they're implemented.

So, if a collection changes very little (compared to accesses) or the changes are concentrated at the end, I'd use a vector.

If the number of changes is substantial (compared to accesses) and they're not at the ends, I'd use a list.

By way of example, reading in a collection at program startup and hardly ever changing it (or if the changes are onlt adding to the end), this would be a good candidate for a vector.

On the other hand, a phone book application for a particularly popular and fickle rock star, I'd be looking towards a list. Actually I'd be looking toward a database connection but that was the best example I could come up with at short notice :-)

As to references, the latest C++0x draft states in part (23.3.4, lists):

A list is a sequence container that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Unlike vectors and deques, fast random access to list elements is not supported.

Section 23.3.5 (on vectors):

A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.

There are a few trade-offs to be considered when choosing between std::list and std::vector.

Also std::list is not about contiguous memory, it can be quite useful if you can't afford iterator invalidation or if you need amortized constant time insertion in the begin/middle/end.