list<T> size

[barcaroller]

Does a list<T> keep track of its size or is the size re-calculated every
time you call list<T>.size()?

 

[Kai-Uwe Bux]

Does a list<T> keep track of its size or is the size re-calculated every
time you call list<T>.size()?

The standard allows for either method. As a consequence, you should call
list<>::size() only when you have to. In particular, prefer

list<>::empty()

to

list<>::size() == 0



Best

Kai-Uwe Bux

 

[Juha Nieminen]

Does a list<T> keep track of its size or is the size re-calculated every
time you call list<T>.size()?

IIRC std::list::size() is *not* guaranteed to be constant-time, and in
most implementations it's indeed linear-time.

I think it has something to do with splice(), but I don't remember the
details.

 

[Guest]

IIRC std::list::size() is *not* guaranteed to be constant-time, and in
most implementations it's indeed linear-time.

I think it has something to do with splice(), but I don't remember the
details.

I think splice must run in O(n), where n is the number of spliced
elements, and that does not allow for recalculating the size when splicing.

 

[Juha Nieminen]

I think splice must run in O(n), where n is the number of spliced
elements, and that does not allow for recalculating the size when splicing.

Don't you mean O(1)?

 

[Markus Moll]

Hi

Don't you mean O(1)?

....where 1 is the number of spliced elements.

SCNR

(It should be O(1) of course)
Markus

 

[Guest]

Don't you mean O(1)?

I was thinking of the version taking a position iterator, a list and two
iterators into this list. It is linear if the provided list is not
*this. Problem is I can no longer remember the reason why this prevents
size() from being O(1).

 

[Pete Becker]

I was thinking of the version taking a position iterator, a list and two
iterators into this list. It is linear if the provided list is not
*this.

It's linear if the provided list has a different allocator from *this.
If the allocators are the same, splice does just what it's name
suggests: it munges a few pointers to snip the specified sublist out of
its current container and insert it directly into the target.

Problem is I can no longer remember the reason why this prevents
size() from being O(1).

The problem is that if splice only needs to munge the end pointers
(i.e. the allocators are the same) it doesn't know how many elements
were inserted.