Re: About std::list
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.
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.
Removing the next to
last element of a vector is just slightly more expensive (one copy of
an element), and so on.
Agreed. The algorithm is to copy the kept elements at the end of the vector
"to the left", overwriting the discarded elements, then finally to destroy
what remains at the end. If an exception is thrown during any of this, the
vector will still be in a valid state, but it won't contain the data it's
supposed to. This is not an issue for list, at least not the copying
aspect, because erasing items from a list doesn't involve copying, just
destruction of the removed items; since destructors shouldn't throw,
exceptions shouldn't be an issue at all.
--
Doug Harrison
Visual C++ MVP