Re: A solution for a fast std::list::size() *and* a fast std::list::splice()
"Juha Nieminen" <nospam@thanks.invalid> wrote in message
news:470e0161$0$27822$39db0f71@news.song.fi...
P.J. Plauger wrote:
-- splice partial contents of another list
The resultant size of the donee list is well known, as is that of any
donating list, in all but the last case. The C++ Standard has
always required that all but the last case be constant time, while
the last one can be linear time.
I can imagine that any algorithm which needs list splicing assumes
that the splicing is constant-time.
You can imagine it. Indeed, several other people have imagined just
that over the past several years. One or two of the brighter ones even
tried to contrive use cases where a partial splice absolutely positively
had to be constant time or the algorithm would be too slow. Every
one of those cases I saw could easily be transmogrified to a case
where the spliced sublist could be made into an entire list, and hence
would splice in constant time.
An obvious case is list::sort, which does a Towers of Hanoi merge
sort by building sublists. The easiest way to implement this is to
minimize the number of temporary lists and splice sublists. But the
common implementation, based on the original H-P STL, uses
more sublists and does complete sublist splices. Hence, the sort
is fastern 'n blazes.
If splice() cannot be assumed to
be
constant-time, then I suppose it becomes a completely useless function
for any purpose you may want to need that operation.
What a crass overstatement. Moreover, in my extensive experience
algorithms with terrible theoretical time complexity almost always
have satisfactory real-world performance because a) data sets
seldom get large enough to matter and b) computers are blindingly
fast for most uses to begin with. In any case, others will find uses
for a linear splice even if you can't.
Any algorithm
needing list splicing would have to implement a list of their own.
Or get one of the implementations that aren't afraid to damage lists
occasionally in the interest of getting fast results all the time.
So the question is: If splice() cannot be assumed to be constant-time,
why support it at all? Better just remove it completely.
See above.
Compare this to eg. std::vector not having a push_front() function:
Since it cannot be done faster than linear time, it's not supported at
all.
Well, that would be one solution -- simply remove the partial splice option.
Note, however, that single-element splice and full-list splice are still
reliably constant-time operations. Or would you have us ditch these too
because people might *fear* they're not going to be fast enough?
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com