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

[Peter Dimov]

Jonathan Wakely wrote:

> 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.

This is only true in theory, but not in practice.

In practice, if all implementations in the known universe have O(1) size, 
such code is portable (and possibly optimal.)

Furthermore, if all implementations except one have O(1) size, and this 
implementation doesn't have some other redeeming qualities that make up for 
it, it's inferior from "free market" point of view (although it may be 
considered superior from "theoretical purity" point of view.)