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

[Howard Hinnant]

On Nov 28, 2005, at 4:58 PM, Gabriel Dos Reis wrote:

> Howard Hinnant <hhinnant@apple.com> writes:
>
> [...]
>
> | These are **your** customers.  By the way they are coding, they are
> | disagreeing with you.
>
> I'm not sure we're going to get anything useful from personalizing the
> debate.

My deepest apologies if I offended, that was not my intent.  I hereby  
owe you a beer (or beverage of your choice) in Berlin. :-)  (they are  
now my customers too and I'm just trying to deliver to them the best  
product I can).

> | We have a serious performance problem today with list.  It does no
> | good to wish it away because we disagree with a decision that was
> | made nearly a decade ago.  We need to deal with the state of affairs
> | as it exists today.
>
> and that is all I'm saying.  I'm not asking you to find a time-travel
> machine and go tell the committee it is making a mistake about
> list<>::size() and change its mind. Maybe someone suggested that, but
> it wasn't me.

If I do find such a machine, I promise never to mention std::list  
again. :-)

> | I have repeatedly tried to back up my opinions with evidence (and
> | spent time gathering it for your benefit) (examples, pointers to
> | actual code, etc.).  I am fully aware of your opinion.  Can you
> | please point me towards supporting evidence so that I can better
> | understand your position?
>
> Well, it has its origin in the design principles underpinning STL.
> STL is not just about funny type names with angle brackets, double
> colon, begin, end, size, and lots of parenthesis.
> The fundamentals are in structuring algorithms/functions and
> algorithmic complexity into concepts and relatives.
>
> Those principles help keep a simple, consistent, efficient interface.

Right!  This is something that goes deep with me too!  list doesn't  
have an operator[] because it would be deceptively inefficient.  Nor  
does it have iter-iter, or iter+n, etc.  All of these would be easy  
to create.  They would just create an inefficient interface.  An O(N)  
size is an inefficient interface.  My "raw numbers" are only  
presented to confirm the theory with practice.

> Permeating the list<> interface with implications of something that
> shouldn't have been there in the first place is a serious deviation.

Ok, so now what?  Don't fix it?

> Now, you're trying to argue from raw numbers.

...

> I guess, we have reached a point where we would just going to
> repeat the same thing over and over again.

I'm trying to not repeat myself, but to offer fresh angles and new  
supporting arguments.  I'm ill-equipped to be both non-repetitive,  
and yet also perfectly constrained to the boundaries of my initial  
argument.

>    (1) what would have been more interesting is the percentage of
>        those usage that are not "hookey usage" of list<>.  I take that
>        percentage to be far compelling.

Every single use that does not compare size() to 0 is not  
"hookey" (imho).  In my previous email that is 3 out of 3 of the  
examples I posted.

>    (2) if we're going to designe the interface governed by raw
>        numbers, then I suggest we remove the invalidation stuff from
>        iterators.  I suspect that the number of applications or
>        programmers that would be saved from those rules would
>        outweight what wouldbe gained from fiddling with list<>
>        interface.
>
> Regarding (2), it can be suspected that the invalidation rules
> actually reflect algorithmic and representational constraints on the
> container anr iterator users.

The interface is already designed.  We are seeing problems in the  
field with the current design.  I (actually we - http://www.open- 
std.org/jtc1/sc22/wg21/docs/papers/2005/n1870.html#require-size-to-be- 
of-constant-complexity) are proposing to tweak the interface based on  
a decade of actual field experience.  Is that not a reasonable course  
of action?

-Howard