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

[Howard Hinnant <hhinnant at apple dot com>]

On Nov 29, 2005, at 8:06 AM, Gabriel Dos Reis wrote:

> The observation is not that size() is never needed ... Using size()  
> must require the same attention as
> choosing the right containers given reference/invalidation constraints
> and algorithmic complexities.

The observation is that this is asking too much from our customers.   
They have been, and will continue to use size() in a manner that  
assumes O(1), not only for std::list, but for every std::container.   
This is not an academic problem.  This is not a problem confined to  
beginners or poor programmers.  Survey code.

In general, the design of the std::lib allowed for this situation.   
For example push_front was purposefully not added to vector because  
clients would likely have mistaken it for an O(1) operation.  Adding  
push_front to vector and simply saying:

> Using push_front() must require the same attention as
> choosing the right containers given reference/invalidation constraints
> and algorithmic complexities.

is just not an acceptable interface design.  It would be an extremely  
error prone interface that would trap beginners and experts alike.   
Claiming that it is a good (or even acceptable) interface would not  
make it so.  A far better interface is to have vector::push_front  
fail at compile time.  There are easy workarounds (like v.insert 
(v.begin(),x)) if the client really wants to do that.

The standard currently requires that all uses of size, max_size and  
swap (for every std::container) must be prepared to assume that the  
operation will be O(N).  Clearly, (very, very clearly if you survey  
any real world code) C++ coders are rejecting these complexity  
requirements en masse.

Note A from 23.1p5 is not only irrelevant with respect to nearly- 
universal C++ coding practice, it is insidiously evil because it  
rarely applies in practice.  But sometimes, and only in some  
implementations, it will reach up and bite the client with absolutely  
no warning.  gcc takes advantage of Note A with std::list::size.   
Dinkumware takes advantage of Note A with any_container::swap when  
the allocators compare not equal.  Both exceptions to the norm break  
real code.

-Howard