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

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

Gabriel Dos Reis wrote:
> "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.

"Conforms to all relevant standards" is a different thing; it means that the 
code is portable in theory, but does not guarantee its portability in 
practice, because implementations may not conform.

"Portable in practice" means that I can move my code from implementation A 
to implementation B and it will still work (well). This is an objective 
measure.

As you point out below, this only holds for a specific point of time. 
However, the natural progression is either (1) for implementations to take 
advantage of the freedom offered by the standard and diverge if there is 
something to be gained, or (2) for the de-facto standard to be codified, as 
was the case with the contiguous storage of std::vector. In principle, you 
could have chosen to implement a non-contiguous vector using the same "their 
code is broken" argument to help users reevaluate their assumptions and fix 
their code.

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

There are good arguments to be made in support of the claim that iterators 
into contiguous storage need to be pointers to allow algorithms to detect 
the case.

But this aside, the point is that we can now look back at several years of 
development and see where the freedom offered by the standard is being taken 
advantage of (vector<>::iterator) and where it is not considered worthwhile 
(list<>::size). No implementation has switched from O(1) to O(N) size, to 
the best of my knowledge.