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

[Howard Hinnant <hhinnant at apple dot com>]

On Nov 24, 2005, at 2:32 PM, Gabriel Dos Reis wrote:

> Since it was a mistake to put it there in the first place, why shall
> we penalize proper list operations by trying to make an error run  
> faster?

"Trying to make an error run faster" implies the wrong thing.  This  
statement is often stated as "why get the wrong answer faster", which  
is something I completely agree with.  An O(1) size doesn't compute  
the wrong answer.  It merely shifts a performance tradeoff.

The status quo (size() may be O(1) or O(N)) is unacceptable because  
people, even experts, will do things like this:

http://home.twcny.rr.com/hinnant/cpp_extensions/ 
On_list_size.html#boost%20survey

It just happens because c.size() is usually O(1) for most c.  We've  
been trained that way.  Having it sometimes be O(N) for some c is  
just error prone, especially in generic code (no different than  
strstream being technically correct and even really useful sometimes,  
but prone to misuse because of a poor interface design, leading to  
memory leaks).

If we want to prevent this mistake from occurring in the future, I  
see only two choices:

1.  Remove list::size.
2.  Make list::size O(1).

Pick the less evil.

Imho, adding a guaranteed O(1) "splice some from other" signature  
helps to make choice 2 a little more palatable.

-Howard