Relative performance of std::vector vs. std::list vs. std::slist?
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?
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.