std::list vs std::vector iteration
c++, iteration, list, stl, vector
Solution
The efficiency gains from cache coherency due to compact representation of data structures can be rather dramatic. In the case of vectors compared to lists, compact representation can be better not just for read but even for insertion (shifting in vectors) of elements up to the order of 500K elements for some particular architecture as demonstrated in Figure 3 of this article by Bjarne Stroustrup:
http://www2.research.att.com/~bs/Computer-Jan12.pdf
(Publisher site: http://www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353)
I think that if this is a critical factor for your program, you should profile it on your architecture.
Problem
It is said that iterating through a vector (as in reading all it's element) is faster than iterating through a list, because of optimized cache. Is there any ressource on the web that would quantify how much it impacts the performances ? Also, would it be better to use a custom linked list, whom elements would be prealocated so that they are consecutive in memory? The idea behind that is that I want to store elements in a certain order that won't change. I still need to be able to insert some at run time in the midle quickly, but most of them will still be consecutive, because the order won't change. Does the fact that the elements are consecutive have an impact in the cache, or because I'll still call `list_element->next` instead of `++list_element` it does not improve anything ?