list<>.size()

list<>.size()

[Michael Vance]

Folks,

Is list<>.size() O(1) for libstdc++ v3? I bring this up because it's
becoming a portability problem for us--on Windows list<>.size is O(1),
so developers will oftentimes write loops with repeated tests against
it. This becomes a speed nightmare when we port these to Linux.

If is not O(1) in libstdc++ v3, I would like to strongly encourage
that it become so :).

Regards,

m.

-- 
Programmer             "Ha ha." "Ha ha." "What are you laughing at?"
Loki Software                      "Just the horror of being alive."
http://lokigames.com/~briareos/                   - Tony Millionaire

Re: list<>.size()

[Daniel Berlin]

On Fri, 31 Mar 2000, Michael Vance wrote:

> Folks,
> 
> Is list<>.size() O(1) for libstdc++ v3?

AFAICT, no.
>  I bring this up because it's
> becoming a portability problem for us--on Windows list<>.size is O(1),
> so developers will oftentimes write loops with repeated tests against
> it. This becomes a speed nightmare when we port these to Linux.
> 
Looking at the STL docs, I don't see size guaranteed to be O(1).
> If is not O(1) in libstdc++ v3, I would like to strongly encourage
> that it become so :).
I don't have the standard in front of me, but if list.size() isn't
guaranteed to be O(1) in complexity, i would strongly encourage your
programs to stop assuming it is.

 > 
> Regards,
> 
> m.

--Dan

Re: list<>.size()

[Michael Vance]

On Fri, Mar 31, 2000 at 05:05:49PM -0800, Daniel Berlin wrote:

> AFAICT, no.

Bummer.

> Looking at the STL docs, I don't see size guaranteed to be O(1).

No, it is not mandated.

> guaranteed to be O(1) in complexity, i would strongly encourage your
> programs to stop assuming it is.

I port code for a living. I have no control over the original
developer's intelligence. But it seems this thing wouild be trivial to
implement and rectify an important porting issue. Changing every

while( list<>.size( ) ) {
       iterator is = list.begin( );
       delete *is;
       list<>.erase( is );
}

is tedious. As is changing every:

if( list<>.size( ) ) {
    // do blah
}

m.

-- 
Programmer             "Ha ha." "Ha ha." "What are you laughing at?"
Loki Software                      "Just the horror of being alive."
http://lokigames.com/~briareos/                   - Tony Millionaire

Re: list<>.size()

[Tudor Hulubei]

  On Friday, 31 March 2000, Michael Vance wrote:
> I port code for a living. I have no control over the original
> developer's intelligence. But it seems this thing wouild be trivial to
> implement and rectify an important porting issue.

What makes you think it is trivial to implement?

Think about splice:

void splice(iterator position, list<T, Alloc>& x, iterator f, iterator l);

This is the corresponding documentation from the STL library:

---
position must be a valid iterator in *this, and [first, last) must be
a valid range in x. position may not be an iterator in the range
[first, last). Splice moves the elements in [first, last) from x to
*this, inserting them before position. All iterators remain valid,
including iterators that point to elements of x. [3] This function is
constant time.
---

Since splice must be O(1), you can't count the elements you move from
one list to another, and therefore it is not possible to keep count of 
the elements in the target list.

Do you have any idea how the Microsoft implementation works so that it 
achieves O(1) for list<>.size()?

Tudor

Re: list<>.size()

[Michael Vance]

On Fri, Mar 31, 2000 at 08:46:00PM -0500, Tudor Hulubei wrote:

> Since splice must be O(1), you can't count the elements you move from
> one list to another, and therefore it is not possible to keep count

You can if the size of those elements is obtainable in O(1) time, as
in the MSVC implementation.

> the elements in the target list.
> 
> Do you have any idea how the Microsoft implementation works so that it 
> achieves O(1) for list<>.size()?

They maintain a size_type member _Size in their list<>. For splice(),
they simple increment _Size by the size of the spliced in list.

Offhand, it appears that the iterators are then undefined...

I'll retract my ill-thought "trivial", but hope to keep this
discussion alive. I seem to remember an interview with one of the
chief STL designers where he stated that list<>.size() should have
been O(1)--did he not support the consistency of iterators after a
splice()?

m.

-- 
Programmer             "Ha ha." "Ha ha." "What are you laughing at?"
Loki Software                      "Just the horror of being alive."
http://lokigames.com/~briareos/                   - Tony Millionaire

Re: list<>.size()

[Michael Vance]

On Fri, Mar 31, 2000 at 09:36:58PM -0600, Raja R Harinath wrote:

> Note that not the whole of 'x' need be spliced in.  How can you figure
> out size([first,last)) in O(1)?

You can't. The MSVC implementation calls distance() on the incoming
list.

Ah well. I have sent a note to the original developers noting that
they are relying upon broken functionality...

m.

-- 
Programmer             "Ha ha." "Ha ha." "What are you laughing at?"
Loki Software                      "Just the horror of being alive."
http://lokigames.com/~briareos/                   - Tony Millionaire

Re: list<>.size()

[llewelly]

On Fri, 31 Mar 2000, Michael Vance wrote:

> On Fri, Mar 31, 2000 at 08:46:00PM -0500, Tudor Hulubei wrote:
> 
> > Since splice must be O(1), you can't count the elements you move from
> > one list to another, and therefore it is not possible to keep count
> 
> You can if the size of those elements is obtainable in O(1) time, as
> in the MSVC implementation.
> 
> > the elements in the target list.
> > 
> > Do you have any idea how the Microsoft implementation works so that it 
> > achieves O(1) for list<>.size()?
> 
> They maintain a size_type member _Size in their list<>. For splice(),
> they simple increment _Size by the size of the spliced in list.
> 
> Offhand, it appears that the iterators are then undefined...
> 
> I'll retract my ill-thought "trivial", but hope to keep this
> discussion alive. I seem to remember an interview with one of the
> chief STL designers where he stated that list<>.size() should have
> been O(1)--did he not support the consistency of iterators after a
> splice()?

http://www.stlport.org/resources/StepanovUSA.html has an interview with
  Alex Stepanov in which he states 'size() used to be linear time in case 
  of STL lists. It was the right decision since if a user wants to keep a
  count it is easy to do, but usually you do not need it and it makes
  splice linear time (it used to be constant). But the standard committee 
  insisted that I change it to constant time. I had no choice. We will
  have to change this requirement eventually.'

[snip]

Re: list<>.size()

[Joe Buck]

> I port code for a living. I have no control over the original
> developer's intelligence. But it seems this thing wouild be trivial to
> implement and rectify an important porting issue. Changing every
> 
> while( list<>.size( ) ) {
>        iterator is = list.begin( );
>        delete *is;
>        list<>.erase( is );
> }
> 
> is tedious. As is changing every:
> 
> if( list<>.size( ) ) {
>     // do blah
> }

Why is this tedious?  You do know about list<...>.empty(), don't you?
The real test here is whether the list is empty and that is guaranteed
to be O(1).  s/size/empty/ in the above.

Re: list<>.size()

[Michael Vance]

On Fri, Mar 31, 2000 at 06:00:10PM -0800, Joe Buck wrote:

> Why is this tedious?  You do know about list<...>.empty(), don't you?

Of course I know about it. It is simple to change those, but any
instance where they *do* wish the size, and not just to know if it's
empty, it is a problem.

It is tedious *because* I have to do it. If I could simply recompile
without having to change this code, my life would be a little less
difficult.

m.

-- 
Programmer             "Ha ha." "Ha ha." "What are you laughing at?"
Loki Software                      "Just the horror of being alive."
http://lokigames.com/~briareos/                   - Tony Millionaire

Re: list<>.size()

[Joe Buck]

> > Why is this tedious?  You do know about list<...>.empty(), don't you?
> 
> Of course I know about it. It is simple to change those, but any
> instance where they *do* wish the size, and not just to know if it's
> empty, it is a problem.

I'm sorry, but you guys signed up to be a porting company, so this is
one of the things you signed up to deal with.

> It is tedious *because* I have to do it. If I could simply recompile
> without having to change this code, my life would be a little less
> difficult.

It does not appear to be possible to make list<...>::size O(1) without
violating the requirements of some of the other STL functions.  Now it
might be possible to produce an almost-O(1) implementation, where some
lists know their size and some (like lists produced by the splice method)
don't, but that would involve changing every method that alters the list
to keep a private member with the correct value.  If you think it would
save you time, one possible approach you could take would be to alter
the list template in that way ... but then you'd have to maintain the
code yourself.

Re: list<>.size()

[Ross Smith]

From: "Joe Buck" <jbuck@possibly.synopsys.com>
> 
> It does not appear to be possible to make list<...>::size O(1) without
> violating the requirements of some of the other STL functions.

I used to think so too, but a careful reading of the standard shows that
this isn't true. The splice() operation is only required to be constant
time when elements are being spliced between locations in the same list
(so size() doesn't change); when the splice is from one list to another,
it may be linear (23.2.2.4 para 14). An implementation like Dinkumware's
(used by MSVC) that keeps an internal size variable, and updates it by
counting elements on splice(), is conforming.

That said, though, an implementation like SGI's (used by GCC) that
doesn't keep such a count, and gives constant-time splice() and linear
size(), is also conforming, and I'm inclined to agree with Alexander
Stepanov that it's preferable. After all, if you're using a list rather
than one of the other containers, presumably it's because you need some
of the specialised list operations (such as splice), so it seems
reasonable to give those operations precedence in efficiency over
operations common to all containers.

-- 
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
   "So that's 2 T-1s and a newsfeed ... would you like clues with that?"
                                                       -- Peter Da Silva

Re: list<>.size()

[Dima Volodin]

It's in the STL FAQ at http://www.sgi.com/Technology/STL/FAQ.html
Look for "Why is list<>::size() linear time?"


On Fri, 31 Mar 2000 16:33:06 -0800, you wrote:

>Folks,
>
>Is list<>.size() O(1) for libstdc++ v3? I bring this up because it's
>becoming a portability problem for us--on Windows list<>.size is O(1),
>so developers will oftentimes write loops with repeated tests against
>it. This becomes a speed nightmare when we port these to Linux.
>
>If is not O(1) in libstdc++ v3, I would like to strongly encourage
>that it become so :).
>
>Regards,
>
>m.
>
>-- 
>Programmer             "Ha ha." "Ha ha." "What are you laughing at?"
>Loki Software                      "Just the horror of being alive."
> http://lokigames.com/~briareos/                   - Tony Millionaire
>