On the performance of forward (linear) iterators of std::vector and std::list

The Experiment

I've been wondering for a while; when iterating linearly over an ordered collection of values; what's faster, an std::list or an std::vector. Today I set up the following C++ experiment:

(univhac.h is an extremely minor project of mine which can be found on http://univhac.googlecode.com/svn/trunk/univhac.h).

I'm only using the last two runs, the first two runs are just to warm up the cache.

The Result

This is with time on the y-axis and the 2-logarithm of the size linear access was tested on on the x-axis. The little disturbances for x < 10 are measurement errors and not repeatable.

Conclusion

Although std::list is slightly faster than std::vector for linear access, the difference on my laptop is maybe 1-2%. So, when all you care about is speed, and all you need is linear access, it really doesn't matter if you pick an std::list or an std::vector. I'd probably go for an std::vector, in case I ever need random access. Now, memory usage is another story, more on that later...