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?

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.

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.