Menu
Possible Duplicate:
When do you prefer using std::list<T> instead of std::vector<T>?
I just watched the recording of the GoingNative'12 talk by Bjarne Stroustrup. And I'm a bit confused.
In this talk he in particular discusses the vector vs list question and suggest that in many cases vector is faster even if you insert and remove intensively to/from the middle, as compilers can optimize a lot of things and like compact structures. And the conclusion(as I understand it) is: first use vector and later think whether you need something else. That sounds reasonable, but taking into account the first observation, what criteria I should take into account? I always thought that if you insert/remove intensively - use list. Similar things are suggested in some topics here. See
Relative performance of std::vector vs. std::list vs. std::slist?
and
vector vs. list in STL
And now according to Stroustrup I was wrong.
Of course I can write a couple of tests and try to figure out what to use in each particular situation, but is there a theoretical way?
318
Vector may have a default size. List does not have default size. In vector, each element only requires the space for itself only. In list, each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
performing a linear search in a vector is several orders of magnitude faster than in a list . the only reason is the usage of the cache line. when a data is accessed, the data is fetched from the main memory to the cache.
For example, taking a bunch of random integers and inserting them in sorted order into a vector or a linked list -- the vector will always be faster, regardless of the number of items total, due to cache misses when searching for the insertion point in the linked list.
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.
The most important motivation for preferring std::list over std::vector is the validity of iterators, not performance. If at the time you're inserting or erasing, you have other iterators into the container, then you probably need std::list, since it insertion doesn't invalidate any iterators, and erasure only invalidates iterators to the element being erased. About the only time std::list will win on performance is when copy and assignment are extremely expensive, and in such cases, it's often a better choice to modify the contained class to reduce the cost of copy and assignment, rather than switching to std::list.
112
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
