by Baptiste Wicht
In C++, two of the most used data structures are
std::list. In this article, their performance is compared in practice on several different workloads.
It is generally said that a
listshould be used when random insert and remove will be performed (performed in O(1) versus O(n) for a
vector). If we look only at the complexity, search in both data structures should be roughly equivalent, complexity being in O(n). When random insert/replace operations are performed on a
vector, all the subsequent data needs to be moved and so each element will be copied. That is why the size of the data type is an important factor when comparing those two data structures.
However, in practice, there is a huge difference, the usage of the memory caches. All the data in a
vectoris contiguous where the
std::listallocates separately memory for each element. How does that change the results in practice ?
This article shows the difference in performance between these two data structures.