[Ed.: Another reason why vector is the default (not only, but preferred) standard container.]

C++ Benchmark: std::vector vs. std::list

by Baptiste Wicht

In C++, two of the most used data structures are std::vector and std::list. In this article, their performance is compared in practice on several different workloads.

It is generally said that a list should 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 vector is contiguous where the std::list allocates 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. 

Continue reading...