Re: About std::list
Doug Harrison [MVP] wrote:
On Sat, 28 Jun 2008 14:03:32 +0200, "Bo Persson" <bop@gmb.dk> wrote:
Jack wrote:
I know I can add/delete items to/from a list at linear time. But
search time thru these lists can be significantly slow. In this
case, should I use a home-brew hash table instead of a list to
gain the benefits of linear time in add/delete and search?
std::vector just won't cut it because it has exponential
add/delete time. Any suggestions?
It also depends on the type of your data. Is it very expensive to
copy? How often do you add and delete elements?
For std::list, complexity of removing an element is actually O(1),
which ignores the constant factor k in k * 1, where k is much
larger than for a std::vector.
Yet in absolute terms, it's still incredibly tiny. It's just a
couple of pointer updates over what std::vector does.
I was thinking more about deallocating the list node. With the default
allocator, that is relatively expensive.
The vector isn't exponential either for a single element, it is
O(N) where N is the size of the vector. Here we have the run time
k * N, but with a *much* smaller k.
The performance also depends on the pattern of your deletes. If you
remove the last element of the vector, that is very cheap - much
cheaper than removing the last element of a list.
Again, I think characterizing the vector operations as "much"
cheaper exaggerates the situation, especially given the OP's
misconceptions about computational complexity.
Ok, for some definition of "much". :-)
Erasing the last element of a vector is about as cheap as it gets. A
common misunderstanding is that O(1) is always the cheapest way to do
something. We both know that the node allocated containers are are not
always the best choice for performance. Using a std::vector often
surprises performancewise, especially if the contained element type
isn't expensive to copy, or likely to throw an exception.
On the other hand, std::list doesn't copy its elements around, but
most implementations excercises the allocator a lot.
Bo Persson