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

[Gabriel Dos Reis]

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. 


[...]

| 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.

[...]

| 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.  

Deviating from those principles -- to be nice to just about everybody
-- usually leads to troubles.  basic_string<> (cited earlier in this
thread) is a wonderful example of such troubles, which just about
everybody is unhappy with and just about everybody is satisfied with.
Or the other way around.  vector<bool> is another one.  I claim we can
trace most of the inconsistencies and troubles with current
specification to  deviations from first principles that make the
general case "right".  A data structure does not acquire a function
just because it is nice to have.

Permeating the list<> interface with implications of something that
shouldn't have been there in the first place is a serious deviation.
For that to be palatable, I believe I would need more evidence than
raw numbers.

You tried earlier to argue from "first principles" that size() shall
be constant-time, I pointed that those first principles were already
weak (and I took your find_or_insert() as implicit agreement.)

Now, you're trying to argue from raw numbers.  Two points:

   (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.

   (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.

-- Gaby