Menu
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?
352
std::vector is insanely faster than std::list to find an element. std::vector performs always faster than std::list with very small data.
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.
Hence std::list provides some extra functions for Sorting, Splicing, Removing elements and identifying unique elements. Vector provides the random access and hence can be used with STL algorithms that uses Random Access Iterators.
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.
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.
149
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.
30
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
