Alf P. Steinbach writes:
* Sam:
Juha Nieminen writes:
Sam wrote:
I'll repeat part of what Richard said for emphasis: "as opposed to
any
of the other standard containers"
Repeating the same question will only yield the same answer: "the
ability to collect a list of numbers, of variable size, then iterate
over them for the purpose of printing them back". If you do not
understand what that means, look it up.
And exactly how is that different from any other STL container?
Why is
std::list the best solution in this case?
Because, in the OP's poster case, his basic demo program did not
require random access, and std::list won't require obtaining the size
of the list in advance, in order to get the best performance.
Hi.
For the OP's purpose, std::vector does not require obtaining the size
of the list in advance (see the push_back() member routine), and has
generally better performance: push_back is of amortized O(1)
complexity. ;-)
I am curious how true it is. So, I decided to measure the performance of
std::vector vs std::list in OP's original context: collect and store a
relatively small list of numbers. How efficient is std::list, versus
std::vector, in creating a small list/vector.
Test program:
int main()
{
size_t j;
for (j=0; j<100000; j++)
{
std::list<int> n;
size_t i;
for (i=0; i<10; i++)
n.push_back(i);
}
return (0);
}
Compiled with gcc 4.4.1. Default compilation options. Three consecutive
runs:
[mrsam@lc2440 tmp]$ time ./t
real 0m0.219s
user 0m0.209s
sys 0m0.002s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.214s
user 0m0.208s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.216s
user 0m0.210s
sys 0m0.002s
Replace std::list with std::vector. The results:
[mrsam@lc2440 tmp]$ time ./t
real 0m0.305s
user 0m0.296s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.304s
user 0m0.297s
sys 0m0.000s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.303s
user 0m0.297s
sys 0m0.001s
Seems fairly consistent -- std::vector is about 30% slower.
Now, using -O2, the results for std::list:
[mrsam@lc2440 tmp]$ time ./t
real 0m0.093s
user 0m0.086s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.093s
user 0m0.086s
sys 0m0.000s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.092s
user 0m0.086s
sys 0m0.001s
and for std::vector:
[mrsam@lc2440 tmp]$ time ./t
real 0m0.111s
user 0m0.105s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.110s
user 0m0.105s
sys 0m0.001s
[mrsam@lc2440 tmp]$ time ./t
real 0m0.110s
user 0m0.104s
sys 0m0.001s
The performance gap has narrowed, somewhat, but std::list still has the
edge.
I guess that's why people are sort of "upset" about your suggestion of
std::list.
Yeah, finding out that they've been barking up the wrong tree, all this
time, can be quite shocking :-).
But std::list is not generally a good *default* choice: it's a very
special purpose structure.
In OP's use case, it does seem to be a better one.