Re: list<>.size()

[<llewelly at dbritsch dot dsl dot xmission dot com>]

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]