vector vs. list in STL

vector:

• Contiguous memory.
• Pre-allocates space for future elements, so extra space required beyond what's necessary for the elements themselves.
• Each element only requires the space for the element type itself (no extra pointers).
• Can re-allocate memory for the entire vector any time that you add an element.
• Insertions at the end are constant, amortized time, but insertions elsewhere are a costly O(n).
• Erasures at the end of the vector are constant time, but for the rest it's O(n).
• You can randomly access its elements.
• Iterators are invalidated if you add or remove elements to or from the vector.
• You can easily get at the underlying array if you need an array of the elements.

list:

• Non-contiguous memory.
• No pre-allocated memory. The memory overhead for the list itself is constant.
• Each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
• Never has to re-allocate memory for the whole list just because you add an element.
• Insertions and erasures are cheap no matter where in the list they occur.
• It's cheap to combine lists with splicing.
• You cannot randomly access elements, so getting at a particular element in the list can be expensive.
• Iterators remain valid even when you add or remove elements from the list.
• If you need an array of the elements, you'll have to create a new one and add them all to it, since there is no underlying array.

In general, use vector when you don't care what type of sequential container that you're using, but if you're doing many insertions or erasures to and from anywhere in the container other than the end, you're going to want to use list. Or if you need random access, then you're going to want vector, not list. Other than that, there are naturally instances where you're going to need one or the other based on your application, but in general, those are good guidelines.

Situations where you want to insert a lot of items into anywhere but the end of a sequence repeatedly.

Check out the complexity guarantees for each different type of container:

What are the complexity guarantees of the standard containers?

If you don't need to insert elements often then a vector will be more efficient. It has much better CPU cache locality than a list. In other words, accessing one element makes it very likely that the next element is present in the cache and can be retrieved without having to read slow RAM.

Most answers here miss one important detail: what for?

What do you want to keep in the containter?

If it is a collection of ints, then std::list will lose in every scenario, regardless if you can reallocate, you only remove from the front, etc. Lists are slower to traverse, every insertion costs you an interaction with the allocator. It would be extremely hard to prepare an example, where list<int> beats vector<int>. And even then, deque<int> may be better or close, not justyfing the use of lists, which will have greater memory overhead.

However, if you are dealing with large, ugly blobs of data - and few of them - you don't want to overallocate when inserting, and copying due to reallocation would be a disaster - then you may, maybe, be better off with a list<UglyBlob> than vector<UglyBlob>.

Still, if you switch to vector<UglyBlob*> or even vector<shared_ptr<UglyBlob> >, again - list will lag behind.

So, access pattern, target element count etc. still affects the comparison, but in my view - the elements size - cost of copying etc.

One special capability of std::list is splicing (linking or moving part of or a whole list into a different list).

Or perhaps if your contents are very expensive to copy. In such a case it might be cheaper, for example, to sort the collection with a list.

Also note that if the collection is small (and the contents are not particularly expensive to copy), a vector might still outperform a list, even if you insert and erase anywhere. A list allocates each node individually, and that might be much more costly than moving a few simple objects around.

I don't think there are very hard rules. It depends on what you mostly want to do with the container, as well as on how large you expect the container to be and the contained type. A vector generally trumps a list, because it allocates its contents as a single contiguous block (it is basically a dynamically allocated array, and in most circumstances an array is the most efficient way to hold a bunch of things).