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