Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?

[Paolo Carlini <pcarlini at suse dot de>]

Howard Hinnant wrote:

>> Thanks! By the way, I'm very puzzled by the words: "... snap shot of
>> boost, just after the release of version 1.33, on Nov. 23, 2005".  Maybe
>> ", just after the release of version 1.33" should go?
>
> <nod>  Yeah, it definitely isn't formal (or precise) wording.  I was 
> just trying to get something up quick (just on my personal website).  
> I might massage it into something readable if I find some cycles.

Humm, maybe you read in my message too much: my point was only that
version 1.33 was released mid of August, more than 3 months ago. Nothing
more.
Personally, I find your document very useful and stimulating, certainly
sufficiently formal at this stage.

> It would also be most interesting if it surveyed something more than 
> boost, or if it at least did a more complete survey of boost.  
> Finding all of the uses of list::size() in generic code is a real 
> problem.  Searching boost sources for size() turns up nearly 2000 
> hits, most of which won't be related to list, but I wouldn't be 
> surprised if a few percent of them were inappropriate calls to 
> list::size() (or could be, depending on template parameters).  But I 
> can't make a career out of manually picking through 2000 calls to size
> () and figuring out which are which. :-)
>
> I realize I've got an uphill (almost sure to loose) battle here.  gcc 
> has had an O(N) list::size for forever.  And the supporters of that 
> decision are numerous, adamant and smart.  When I considered gcc's 
> libstdc++ a competitor, I actually took comfort in that fact, secure 
> in the knowledge that gcc would never come around and challenge me in 
> that department.  If gcc's customer base mysteriously saw significant 
> performance gains when migrating to my product, that was a good 
> thing! ;-)  Now, ironically, I find myself in a position of trying to 
> argue for the very change that I took comfort in believing would 
> never happen. :-)

Personally, again, my only very serious concern is binary compatibility,
due to the additional storage of the size, which in any case will delay
this kind of change to the next library ABI. Otherwise, I would
certainly not resist to compelling evidence from actual usage that O(1)
is a must and much more important than splice.

By the way, in my opinion Matt has a very good point that a size, in
principle, could be always *added* in user code, outside std::list
proper. I think that option overall leads to a third set of trade-offs.
It would be nice if a paper summarizing the issue could also compare to
that option (i.e., would be: O(N) size, O(1) size, O(N) size + external
size).

> My position isn't that a doubly-linked list should have an O(1) 
> size.  It is that if a container, any container, has a size(), then 
> that member should be O(1) (same for operator[], at, swap, max_size, 
> capacity, begin, end, front, back, push/pop_front, push/pop_back, 
> empty, default ctor,  -- perhaps amortized O(1) on some of those).  
> It would be incredibly easy to give std::list an operator[].  It 
> would also be an incredibly bad idea.

Agreed.

> std::list has a size().  We should either get rid of it, or make it O
> (1).  Having it there, and (maybe) be O(N) is nothing but a bear trap 
> waiting to spring on the next person that comes to C++ and hasn't yet 
> memorized Scott's Effective STL (btw I haven't memorized that 
> valuable book either).  I think getting rid of list::size is too big 
> of a backwards compatibility hit.
>
> Yes, I'm aware of the size-cache compromise solution (size() is O(1) 
> until splice invalidates it).  I worry about:
>
> for (int i = 0; i < list.size(); ++i)
> {
>     ...
>     list.splice(list.end(), other_list, ol1, ol2);
>     ...
> }
>
> I think
>
>     void splice(iterator position, list& x, iterator first, iterator 
> last, size_type n);  // must be O(1)
>
> is a better compromise.  I also realize that it *is* a compromise, 
> and not a 100% solution.

Well, somehow I like it, but certainly I find it "weird", don't know how
to better explain. I don't think there is something similar elsewhere in
the library: a quantity that the library could compute by itself and is
instead passed by the user with the requirement that must be consistent
with what the library would compute. Weird! ;)

Paolo.