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

[Gabriel Dos Reis]

"Peter Dimov" <pdimov@mmltd.net> writes:

| 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 there is no standard guarantee than a semantics
constraint hold, then the code is probably not protable.  The place we
usually give such guarantee is in the standard specification.  That is
not theory.

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

At one point, all known implementations were using T* for
vector<T>::iterator; people made reasoning similar to the above and 
later found that they had to re-evaluiate their assumptions.

-- Gaby