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

[Jonathan Wakely <cow at compsoc dot man dot ac dot uk>]

On Tue, Nov 29, 2005 at 01:58:11AM +0100, Gabriel Dos Reis wrote:
> 
>    (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.

I think we all agree that if performance of anything except splicing is
really important, then std::list is often the wrong choice, right?

I'm definitely in the school of thought that says that if performance
really matters, then competent programmers should be quite capable of
researching the performance tradeoffs of the std containers and coming
to a sensible conclusion.  "I have a list of employees, therefore I
should use std::list" is lazy and plain wrong.

The fact that good programmers do rely on O(1) list::size() in real code
doesn't change the fact that such code is buggy (or, at least,
sub-optimal).

If libstdc++ did provide an O(1) list::size() programmers still
couldn't rely on it in portable code - so they still *shouldn't* rely
on it.  So only sub-optimal, non-portable code would be helped.

jon