[c++] vector vs. list in STL



Answers

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.

Question

I noticed in Effective STL that

vector is the type of sequence that should be used by default.

What's does it mean? It seems that ignore the efficiency vector can do anything.

Could anybody offer me a scenario where vector is not a feasible option but list must be used?




The only hard rule where list must be used is where you need to distribute pointers to elements of the container.

Unlike with vector, you know that the memory of elements won't be reallocated. If it could be then you might have pointers to unused memory, which is at best a big no-no and at worst a SEGFAULT.

(Technically a vector of *_ptr would also work but in that case you are emulating list so that's just semantics.)

Other soft rules have to do with the possible performance issues of inserting elements into the middle of a container, whereupon list would be preferable.




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 loose 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're 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.




Basically a vector is an array with automatic memory management. The data is contiguous in memory. Trying to insert data in the middle is a costly operation.

In a list the data is stored in unrelated memory locations. Inserting in the middle doesn't involve copying some of the data to make room for the new one.

To answer more specifically your question I'll quote this page

vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.




Preserving the validity of iterators is one reason to use a list. Another is when you don't want a vector to reallocate when pushing items. This can be managed by an intelligent use of reserve(), but in some cases it might be easier or more feasible to just use a list.




Well the students of my class seems quite unable to explain to me when it is more effective to use vectors, but they look quite happy when advising me to use lists.

This is how I understand it

Lists: Each item contains an address to the next or previous element, so with this feature, you can randomize the items, even if they aren't sorted, the order won't change: it's efficient if you memory is fragmented. But it also has an other very big advantage: you can easily insert/remove items, because the only thing you need to do is change some pointers. Drawback: To read a random single item, you have to jump from one item to another until you find the correct address.

Vectors: When using vectors, the memory is much more organized like regular arrays: each n-th items is stored just after (n-1)th item and before (n+1)th item. Why is it better than list ? Because it allow fast random access. Here is how: if you know the size of an item in a vector, and if they are contiguous in memory, you can easily predict where the n-th item is; you don't have to browse all the item of a list to read the one you want, with vector, you directly read it, with a list you can't. On the other hand, modify the vector array or change a value is much more slow.

Lists are more appropriate to keep track of objects which can be added/removed in memory. Vectors are more appropriate when you want to access an element from a big quantity of single items.

I don't know how lists are optimized, but you have to know that if you want fast read access, you should use vectors, because how good the STL fasten lists, it won't be as fast in read-access than vector.






Links