Relative performance of std :: vector vs std :: list vs. std :: slist?

Question

For a simple linked list in which random access to list items is not a requirement, are there any significant benefits (performance or otherwise) for using std::list instead of std::vector ? If std::slist is required, would it be more efficient to use the std::slist and reverse() list before iterating over its elements?

Answer 1

As usual, the best answer to performance questions is profile both versions for your use case and see which is faster.

In the general case, if you have inserts in the data structure (except for the end), then vector can be slower, otherwise in most cases vector is expected to be better than list , if only for a problem with data locality , this means that if there are two elements, which are adjacent in the data set, adjacent in memory, then the next element will already be in the processor cache and will not need to print pages in memory.

Also keep in mind that the overhead of the space for vector is constant (3 pointers), while the overhead of the space for list paid for each element, this also reduces the number of full elements (data plus overhead) that can be cached in any moment in time.

Answer 2

The default data structure that you need to think about in C ++ is Vector .

Consider the following points ...

1] Bypass:
List nodes are scattered throughout the memory, and therefore traversing the list leads to misses in the cache . But vector traversal is smooth.

2] Insert and delete:
The average 50% of the elements should be shifted when you do this with Vector, but the caches are very good at that! But, with lists, you need to go to the insert / delete point ... so again ... cache misses! And surprisingly, vectors also win this case!

3] Storage:
When you use lists, there are two pointers to elements (forward and backward), so the list is much larger than the vector! Vectors require a bit more memory than actual elements need.

Yout must have a reason not to use a vector.

---

Reference:
I found out about this in a conversation with Lord Bjarn Straustup: https://youtu.be/0iWb_qi2-uI?t=2680

Answer 3

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

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

Understand how these collections are implemented: a vector is a sequential array of data, a list is an element containing data and pointers to the following elements. Once you understand this, you will understand why lists are good for inserts and bad for random access.

(therefore, the reverse iteration of the vector is exactly the same as for the direct iteration - the iterator simply subtracts the size of the data elements each time, the list should still go to the next element using the pointer)

Answer 4

If you need a reverse move, then slans are unlikely to become your data structure.

A regular (double) linked list gives you constant insertion and deletion times anywhere in the list; the vector only gives the default insert and delete at the end of the list. For a vector, insertion and deletion times are linear anywhere except at the end. This is not the whole story; There are also constant factors. A vector is a simpler data structure that has advantages and disadvantages depending on the context.

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

Answer 5

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

As others have noted, for most things, it is best to use std :: vector continuous storage. There is practically no reason to use std :: list, with the exception of small amounts of data (where they can all be included in the cache) and / or where erasure and re-entry often occur. The guarantees of complexity do not apply to real performance due to the difference between the cache and the main memory speeds (200x) and how continuous access to the memory affects the use of the cache. See Chandler Carruth (google) about the problem here: https://www.youtube.com/watch?v=fHNmRkzxHWs

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

Answer 6

See this question for pricing details:
What is the difficulty of Standard Container Warranties

If you have a slider, and now you want to go through it in reverse order, why not change the type that will be displayed everywhere?