Finally, we can also test a number crunching operation. Here, random elements are inserted into the container that is kept sorted. It means, that the position where the element has to be inserted is first searched by iterating through elements and the inserted. As we talk about number crunching, only 8 bytes elements are tested.
We can clearly see that vector is more than an order of magnitude faster than list and this will only be more as the size of the collection increase. This is because traversing the list is much more expensive than copying the elements of the vector.
To conclude, we can get some facts about each data structure:
- std::vector is insanely faster than std::list to find an element
- std::vector performs always faster than std::list with very small data
- std::vector is always faster to push elements at the back than std::list
- std::list handles very well large elements, especially for sorting or inserting in the front
This draw simple conclusions on usage of each data structure:
- Number crunching: use std::vector
- Linear search: use std::vector
- Random Insert/Remove: use std::list (if data size very small (< 64B on my computer), use std::vector)
- Big data size: use std::list (not if intended for searching)
If you have the time, in practice, the best way to decide is always to benchmark both versions, or even to try another data structures.
I hope that you found this article interesting. If you have any comment or have an idea about an other workload that you would like to test, don’t hesitate to post a comment If you have a question on results, don’t hesitate as well.
The code source of the benchmark is available online: https://github.com/wichtounet/articles/blob/master/src/vector_list/bench.cpp