Relative performance of std::vector vs. std::list vs. std::slist?


Question

For a simple linked list in which random access to list elements is not a requirement, are there any significant advantages (performance or otherwise) to using std::list instead of std::vector? If backwards traversal is required, would it be more efficient to use std::slist and reverse() the list prior to iterating over its elements?

1
49
10/26/2008 1:24:34 PM

Accepted Answer

As usual the best answer to performance questions is to profile both implementations for your use case and see which is faster.

In general if you have insertions into the data-structure (other than at the end) then vector may be slower, otherwise in most cases vector is expected to perform better than list if only for data locality issues, this means that if two elements that are adjacent in the data-set are adjacent in memory then the next element will already be in the processor's cache and will not have to page fault the memory into the cache.

Also keep in mind that the space overhead for a vector is constant (3 pointers) while the space overhead for a list is paid for each element, this also reduces the number of full elements (data plus overhead) that can reside in the cache at any one time.

58
5/23/2017 11:47:36 AM

Default data structure to think of in C++ is the Vector.

Consider the following points...

1] Traversal:
List nodes are scattered everywhere in memory and hence list traversal leads to cache misses. But traversal of vectors is smooth.

2] Insertion and Deletion:
Average 50% of elements must be shifted when you do that to a Vector but caches are very good at that! But, with lists, you need to traverse to the point of insertion/deletion... so again... cache misses! And surprisingly vectors win this case as well!

3] Storage:
When you use lists, there are 2 pointers per elements(forward & backward) so a List is much bigger than a Vector! Vectors need just a little more memory than the actual elements need.

Yout should have a reason not to use a vector.


Reference:
I learned this in a talk of The Lord Bjarne Stroustrup: https://youtu.be/0iWb_qi2-uI?t=2680


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon