First a suggestion: You probably want to wait more than a couple of minutes before accepting an answer: You'll probably get more answers that way.
Second: when benchmarking, you should always compile with optimizations turned on. Something like
g++ -std=c++11 -O3 -march=native should get you good results.
std::list really is a poor data structure, and I have not yet found a situation in which it is the best. For instance, consider the case where you want to maintain a sorted data structure. You may think that
O(1) insertion and deletion time would be ideal, but in fact, it is sub-optimal!
For these tests, my contained type is a trivial class that contains an array of 4-byte integers. I test a
std::array of size 1, 10, and 100 (giving me an element size of 4, 40, and 400). I chose a
std::array because a move and a copy are the same thing. The initial element of the array is initialized to some random number between
std::numeric_limits<uint32_t>::max(). I create a
std::vector of some number of these (the x-axis), then I start the timer. I test iterating over that
std::vector for each element and inserting it in order (as sorted by that first element in the array, using
operator<=). To help avoid any clever compiler optimizations of removing any work, I then output the first element of the sorted container (which cannot be determined until the end) to some file and stop the timer.
These are my results for various sizes of elements:
We see that for 4 and 40 byte elements,
std::vector is better even at this inserting into the middle than
std::list, and for any element size you're better off using a
In general, I cannot come up with a reason to use
std::list over a class that wraps
std::vector<std::unique_ptr> to make it appear as though it has value semantics, other than the ability to copy (which I hope to fix by either submitting a
value_ptr class to Boost if one isn't added soon, although there is discussion about that).
As an additional note, if this were real code, not a comparison / benchmark game, I would have written the
std::vector version much more differently. I would have copied the entire original container directly, then used
std::sort. I intend to write a more complete analysis on data structures, with a focus on the importance of data locality, and I will include timing on the "correct" way to do it. (the correct version blows all other methods out of the water, completing in much less than a second for 400,000 elements of size 400, which is 10 times more elements than I tested in my graphs).
I hope I explained everything well; these are some tests I ran several months ago and haven't yet finished my notes on the subject.
Tests were done on an Intel i5 machine with 4 GiB of RAM. I believe I was using Fedora 17 x64.