Hi
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 that vector is not a feasible option but list must be used?
Thanks!
When you have a lot of insertion or deletion in the middle of the sequence. e.g. a memory manager.
Situations where you want to insert a lot of items into the middle of a sequence repeatadly.
Check out the complexity gurantees for each different types of container:
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.
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.
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.
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).
When you want to move objects between containers, you can use list::splice.
For example, a graph partitioning algorithm may have a constant number of objects recursively divided among an increasing number of containers. The objects should be initialized once and always remain at the same locations in memory. It's much faster to rearrange them by relinking than by reallocating.
Edit: as libraries prepare to implement C++0x, the general case of splicing a subsequence into a list is becoming linear complexity with the length of the sequence. This is because splice (now) needs to iterate over the sequence to count the number of elements in it. (Because the list needs to record its size.) Simply counting and re-linking the list is still faster than any alternative, and splicing an entire list or a single element are special cases with constant complexity. But, if you have long sequences to splice, you might have to dig around for a better, old-fashioned, non-compliant container.
vector:
list:
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.
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.