Benefit of slist over vector?

Question

What I need is just a dynamically growing array. I don't need random access, and I always insert to the end and read it from the beginning to the end.

slist seems to be the first choice, because it provides just enough of what I need. However, I can't tell what benefit I get by using slist instead of vector. Besides, several materials I read about STL say, "vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence". Therefore, my question is: for my needs, is slist really a better choice than vector? Thanks in advance.

Answer 1

For starters, slist is non-standard.

For your choice, a linked list will be slower than a vector, count on it. There are two reasons contributing to this:

1. First and foremost, cache locality; vectors store their elements linearly in the RAM which facilitates caching and pre-fetching.
2. Secondly, appending to a linked list involves dynamic allocations which add a large overhead. By contrast, vectors most of the time do not need to allocate memory.

However, a std::deque will probably be even faster. In-depth performance analysis has shown that, despite bias to the contrary, std::deque is almost always superior to std::vector in performance (if no random access is needed), due to its improved (chunked) memory allocation strategy.