Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > A solution for a fast std::list::size() *and* a fast std::list::splice()

Reply
Thread Tools

A solution for a fast std::list::size() *and* a fast std::list::splice()

 
 
Juha Nieminen
Guest
Posts: n/a
 
      10-10-2007
If I'm not completely mistaken, the only reason why std::list::size()
may be (and usually is) a linear-time operation is because they want
std::list::splice() to be a constant-time operation, and if you execute
the latter, the size of the resulting lists cannot be known without
explicitly counting the sizes of the new lists.

I was thinking: What if size() was an O(n) operation only *after*
a splice() operation has been performed (and only the first time size()
is called after that), but O(1) otherwise?

In other words, keep a size variable in the list class and update
it as necessary, and additionally keep a flag which tells if this
size variable is valid. As long as the flag tells that it's valid,
list::size() can return the value of the variable. Only if the flag
says it's invalid, then the O(n) counting will be performed, updating
the variable, after which the flag can be set to valid.

A splice() operation would set the flag to invalid in both lists.

This way splice() will always be O(1), and size() will be O(n) only
once after a splice(), but O(1) otherwise. You will get speed benefits
in all cases except if you alternatively call splice() and size()
repeatedly (in which case you just get the same behavior as in most
current list implementations, so it's not like the result would be
worse).
 
Reply With Quote
 
 
 
 
tony_in_da_uk@yahoo.co.uk
Guest
Posts: n/a
 
      10-10-2007
On Oct 10, 9:50 am, Juha Nieminen <(E-Mail Removed)> wrote:
> In other words, keep a size variable in the list class and update
> it as necessary, and additionally keep a flag which tells if this
> size variable is valid. As long as the flag tells that it's valid,
> list::size() can return the value of the variable. Only if the flag
> says it's invalid, then the O(n) counting will be performed, updating
> the variable, after which the flag can be set to valid.
>
> A splice() operation would set the flag to invalid in both lists.


All sensible and in my opinion useful, but there are people who're
already using lists who wouldn't want them to slow down, or grow their
data member size - even a little bit - to maintain this extra state.
You can easily provide this in a wrapper class around the STL, and
publish it if you think others would want it. Maybe even submit it to
boost....

Tony

 
Reply With Quote
 
 
 
 
Jerry Coffin
Guest
Posts: n/a
 
      10-10-2007
In article <470c2093$0$27815$(E-Mail Removed)>,
http://www.velocityreviews.com/forums/(E-Mail Removed)lid says...
> If I'm not completely mistaken, the only reason why std::list::size()
> may be (and usually is) a linear-time operation is because they want
> std::list::splice() to be a constant-time operation, and if you execute
> the latter, the size of the resulting lists cannot be known without
> explicitly counting the sizes of the new lists.
>
> I was thinking: What if size() was an O(n) operation only *after*
> a splice() operation has been performed (and only the first time size()
> is called after that), but O(1) otherwise?


This is a perfectly legitimate way of implementing std::list. It's not
required, of course, but you can do it if you want to. Then again, you
can't count on it in general.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      10-10-2007
(E-Mail Removed) wrote:
> All sensible and in my opinion useful, but there are people who're
> already using lists who wouldn't want them to slow down


This solution would only speed it up. The alternative is to use
the current typical solution, which is an O(n) size() function.

> or grow their data member size


The size of the list elements would not change at all. Only the
size of the std::list class would grow by one flag and one size
variable. Hardly catastrophical (especially taking into account
how much it speeds up size()).

> You can easily provide this in a wrapper class around the STL


Can I? I would have to reimplement most of the list member functions.
Not a trivial task.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      10-10-2007
Jerry Coffin wrote:
> This is a perfectly legitimate way of implementing std::list.


If it's a perfectly working solution, why aren't they using it
to implement std::list? It sounds quite an obvious solution to me.
 
Reply With Quote
 
=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=
Guest
Posts: n/a
 
      10-10-2007
On 2007-10-10 15:31, Juha Nieminen wrote:
> Jerry Coffin wrote:
>> This is a perfectly legitimate way of implementing std::list.

>
> If it's a perfectly working solution, why aren't they using it
> to implement std::list? It sounds quite an obvious solution to me.


First figure out who have not implemented list in that way (there are
many vendors of C++ standard libraries) and then ask them. My guess
would be that the value of optimisations not guaranteed in the standard
is debatable, the users could never depend on them.

--
Erik Wikström
 
Reply With Quote
 
Michael DOUBEZ
Guest
Posts: n/a
 
      10-10-2007
Juha Nieminen a écrit :
> Jerry Coffin wrote:
>> This is a perfectly legitimate way of implementing std::list.

>
> If it's a perfectly working solution, why aren't they using it
> to implement std::list? It sounds quite an obvious solution to me.


Perhaps because nobody needs it and if you need it, it is
straightforward to add it.

From a design point of view, you rarely need to know the size of a list.

Michael
 
Reply With Quote
 
Bo Persson
Guest
Posts: n/a
 
      10-10-2007
Juha Nieminen wrote:
:: Jerry Coffin wrote:
::: This is a perfectly legitimate way of implementing std::list.
::
:: If it's a perfectly working solution, why aren't they using it
:: to implement std::list? It sounds quite an obvious solution to me.

But it still makes the size() call O(n). The fact that it sometimes
(often) is O(1) doesn't help me writing a function that uses
list::size().

How would I know if someone had called splice recently? So I would
still have to assume O(n) !



Bo Persson


 
Reply With Quote
 
P.J. Plauger
Guest
Posts: n/a
 
      10-10-2007
----- Original Message -----
From: "Juha Nieminen" <(E-Mail Removed)>
Newsgroups: comp.lang.c++
Sent: Tuesday, October 09, 2007 20:50
Subject: A solution for a fast std::list::size() *and* a fast
std::list::splice()

> If I'm not completely mistaken, the only reason why std::list::size()
> may be (and usually is) a linear-time operation


It's a constant time operation in our implementation, and always
has been.

> is
> because they want
> std::list::splice() to be a constant-time operation, and if you execute
> the latter, the size of the resulting lists cannot be known without
> explicitly counting the sizes of the new lists.


There are three forms of splice:

-- splice a single element from this or another list

-- splice the entire contents of another list

-- 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.

Moreover, in all but the last case it's a trivial matter to preserve
the integrity of both donor and donee. In the last case the only
way to avoid pirating the head node of another list is to walk
the donated sublist looking for that head node. It's a trivial
matter to count up the nodes while you're doing this very useful
checking. Some of us think this checking is absolutely essential.

> I was thinking: What if size() was an O(n) operation only *after*
> a splice() operation has been performed (and only the first time size()
> is called after that), but O(1) otherwise?
>
> In other words, keep a size variable in the list class and update
> it as necessary, and additionally keep a flag which tells if this
> size variable is valid. As long as the flag tells that it's valid,
> list::size() can return the value of the variable. Only if the flag
> says it's invalid, then the O(n) counting will be performed, updating
> the variable, after which the flag can be set to valid.
>
> A splice() operation would set the flag to invalid in both lists.
>
> This way splice() will always be O(1), and size() will be O(n) only
> once after a splice(), but O(1) otherwise. You will get speed benefits
> in all cases except if you alternatively call splice() and size()
> repeatedly (in which case you just get the same behavior as in most
> current list implementations, so it's not like the result would be
> worse).


This discussion comes up about once a year, and this solution is
offered each time. I consider it mooted by the need to check a
partial splice anyway, which takes linear time. Other disagree,
so YMMV.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      10-11-2007
In article <470cd502$0$3192$(E-Mail Removed)>,
(E-Mail Removed)lid says...
> Jerry Coffin wrote:
> > This is a perfectly legitimate way of implementing std::list.

>
> If it's a perfectly working solution, why aren't they using it
> to implement std::list? It sounds quite an obvious solution to me.


Some of them are, at least when it's practical. It seems like this comes
up around every 10 months or so, and as I recall the last time it did
either P.J. Plaugar or Pete Becker (who was still working for Dinkumware
around then) pointed out that under most circumstances, Dinkumware's
implementation does execute in constant time. In fact, this post will
probably cross with another that says essentially the same thing again.

You still can't depend on it though, and I don't know how to make
list::size() execute in cosntant time without forcing list::splice
require linear time in at least some cases. 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.

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).

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C++ solution for K & R(2nd Ed) Ex.6-4 - better solution needed subramanian100in@yahoo.com, India C++ 17 10-01-2007 09:00 AM
Solution file not in the solution folder =?Utf-8?B?Y2FzaGRlc2ttYWM=?= ASP .Net 2 09-12-2006 11:04 AM
A Solution using Tasks Re: [Stackless] Suggestion for a Solution ? Andrew Francis Python 0 06-28-2006 06:05 PM



Advertisments