Re: A solution for a fast std::list::size() *and* a fast std::list::splice()
Jerry Coffin wrote:
Given the frequency with
which I've seen good uses for std::list::size() (i.e. essentially never)
I'm not sure that would be a good tradeoff.
In my proposed solution splice() would still be constant-time. Only
size() would be faster (except immediately after a splice()). I see
no "tradeoff" here. It's pure speedup with no negative side-effects.
Granted, in the vast majority of cases where lists are useful knowing
its size is usually unneeded (because a list is the kind of data
structure where its size is not really that important because more often
than not you are only interested in either the first/last item, or all
the items at the same time, and even if you are interested in one single
item somewhere in the list, you are going to have to traverse it anyways).
However, the problem with list::size() is that most people who don't
know it can be linear time may well assume it's constant-time because
it's constant-time in all the other STL data containers too, and thus
they will carelessly use list::size() without giving it a second
thought, thus resulting in needlessly inefficient programs. If
list::size() can be made faster without affecting negatively anything
else, I don't see any reason why it couldn't be done.
Then again, I have to admit that I tend to think the presence of
std::list does more harm than good, since its presence seems to give
soem people the idea that they should use it, and over time I've become
convinced that suitable uses for linked lists are about as common as
magnetic monopoles (i.e. they should theoretically exist, but the few
times people think they might have seen one in reality, confirmation
seems impossible).
I have used std::list for useful purposes many times. Linked lists
have certain useful properties when you know how to use them.
It would be a real pain to have to re-implement linked lists every
time I need one.