This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
"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