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?

Solution 1

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.

Solution 2

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.

---

https://youtu.be/0iWb_qi2-uI?t=2680

Solution 3

Simply no. List has advantages over Vector, but sequential access is not one of them - if that's all you're doing, then a vector is better.

However.. a vector is more expensive to add additional elements than a list, especially if you're inserting in the middle.

Understand how these collections are implemented: a vector is a sequential array of data, a list is an element that contains the data and pointers to the next elements. Once you understand that, you'll understand why lists are good for inserts, and bad for random access.

(so, reverse iteration of a vector is exactly the same as for forward iteration - the iterator just subtracts the size of the data items each time, the list still has to jump to the next item via the pointer)

Solution 4

If you need backwards traversal an slist is unlikely to be the datastructure for you.

A conventional (doubly) linked list gives you constant insertion and deletion time anywhere in the list; a vector only gives amortised constant time insertion and deletion at the end of the list. For a vector insertion and deletion time is linear anywhere other than the end. This isn't the whole story; there are also constant factors. A vector is a more simple datastructure that has advantages and disadvantages depending on the context.

The best way to understand this is to understand how they are implemented. A linked list has a next and a previous pointer for each element. A vector has an array of elements addressed by index. From this you can see that both can do efficient forwards and backwards traversal, while only a vector can provide efficient random access. You can also see that the memory overhead of a linked list is per element while for the vector it is constant. And you can also see why insertion time is different between the two structures.

Solution 5

Some rigorous benchmarks on the topic: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

As has been noted by others, contiguous memory storage means std::vector is better for most things. There is virtually no good reason to use std::list except for small amounts of data (where it can all fit in the cache) and/or where erasure and reinsertion are frequent. Complexity guarantees do Not relate to real-world performance because of the difference between cache and main memory speeds (200x) and how contiguous memory access affects cache usage. See Chandler Carruth (google) talk about the issue here: https://www.youtube.com/watch?v=fHNmRkzxHWs

And Mike Acton's Data Oriented Design talk here: https://www.youtube.com/watch?v=rX0ItVEVjHc

View more solutions

Comments

[Motti]

An important point is that lists have additional pointers per element while a vector just has three pointers for the whole data structure.

[janm]

Yes, that's true: My response says: "A linked list has a next a previous pointer for each element. A vector has an array of elements addressed by index." Clearly the word "and" is missing(!) and I'll make the extra pointers clear.

[Talia]

Keep in mind also that even insertions are faster in a vector than in a linked list if the location to insert into has to be searched for. For example, taking a bunch of random integers and inserting them in sorted order into a vector or a linked list -- the vector will always be faster, regardless of the number of items total, due to cache misses when searching for the insertion point in the linked list.

[Talia]

Pretty much the only place where a linked list is faster is when you are doing a lot of splicing, since that does not involve a large number of cache misses, and each splice is a constant-time operation (which can move a large number of items from one linked list to another).

[Sam Washburn]

I think you mean cache miss, but as an indie game developer the code I write has also had some cash misses too.

[gulgi]

java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs Kindof same thing as Bjarne says, but with better numbers and source code for the tests.

[Admin]

This is the obvious, and 99% of the time, correct answer. If you need backwards traversal run your for loop backwards. Arrays/Vectors provide random access, very fast sequential access, and equally fast sequential access from any random starting point in the vector. Liked lists have only one forte', and that is deleting members or inserting members at some point along the list. They pretty much suck at everything else. Slow, slow, slow. Growing an array/vector is as easy as a new malloc() and memmove(). Using Vprime, Vgrow, you can just realloc them and copy back and forth.

[Mooing Duck]

"Also keep in mind that the space overhead for a vector is constant" Only if you're very very careful. For casual usage, it has linear space overhead, same as a list. See: amortized linear push_back.

[Motti]

@MooingDuck you're right that at the worst case vector will allocate twice as much space as it needs but all but a constant part of this space is cold and won't cause any additional cache hits.

[Serge Rogatch]

@gulgi , that link deserves a separate answer, not just a comment. It would be nice to have the graph and short explanations here on Stackoverflow.