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

["Peter Dimov" <pdimov at mmltd dot net>]

Howard Hinnant wrote:

> Actually I was thinking that size() may have better fit into the
> "Optional sequence operations" table (i.e. only if O(1)).  And so
> yes, if f positively needed the size information, c.size() would
> generate an error if C could not provide it (same rationale as for
> all other members of the optional sequence operations).  The compile
> time error in this case would be a feature, not a bug.

At the moment, I can't think of a container that would be enhanced by _not_ 
providing an "amortized constant" size().

I've been writing "concurrent" containers recently, and in some cases, not 
keeping track of the size can simplify the implementation a lot; even so, I 
had to provide size() because either the container needed it internally, or 
there were legitimate scenarios in which the user needed it (for monitoring 
purposes, for example.)