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

[Howard Hinnant]

On Nov 24, 2005, at 4:32 AM, Gabriel Dos Reis wrote:

> | My position isn't that a doubly-linked list should have an O(1)   
> size.
> | It is that if a container, any container, has a size(), then  that
> | member should be O(1) (same for operator[], at, swap, max_size,
> | capacity, begin, end, front, back, push/pop_front, push/pop_back,
> | empty, default ctor,  -- perhaps amortized O(1) on some of those).
>
> so the next battle is to make map<>::operator[] O(1)?
> That one might be more useful to me than making list<>::size O(1) ;-p

Sarcasm aside, when I first started implementing that function years  
ago, I renamed the underlying implementation "find_or_insert" just so  
that I could remember what the thing did.  Over the years I've gotten  
use to the name of map::operator[].  But I clearly remember being  
confused by it (but then I'm easily confused! :-)).

-Howard