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?
C++ – Relative performance of std::vector vs. std::list vs. std::slist
cdata structureslinked listperformancestl
Related Topic
- Python – the difference between Python’s list methods append and extend
- C++ – The Definitive C++ Book Guide and List
- C++ – Why is “using namespace std;” considered bad practice
- Sqlite – Improve INSERT-per-second performance of SQLite
- C++ – the easiest way to initialize a std::vector with hardcoded elements
- C++ – Why does changing 0.1f to 0 slow down performance by 10x
- C# – System.Windows.Application.GetResourceStream returns null
Best 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 casesvector
is expected to perform better thanlist
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 alist
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.