Re: [Monotone-devel] Re: using empty() instead of size()

[Ulf Ochsenfahrt]

Bruce Stephens wrote:
> Ulf Ochsenfahrt <address@hidden> writes:
>
> [...]
>
> > What about inifinite loops? The linked list could also loop back to itself.
>
> Is there any guarantee that a std::list is a linked list?  Is it
> possible to produce a cycle in a std::list?  Is the behaviour of
> size() on such a list defined?

You can access arbitrary memory in C++, so, yes, it is possible. Though 
probably not through the usual std::list api. This ability essentially 
subverts the type system, making otherwise possible optimizations 
potentially dangerous. (Though I hear about differences between O2 and 
O3 compiled code often enough, so the gcc writers apparently sometimes 
make such decisions.)

A friend of mine implemented a gcc extension that checked all memory 
accesses, and tested it on 2 or 3 open source projects, and at least one 
of them used direct memory access as a feature. It specifically edited 
in-memory data structures it knew were there.

> Even for a program whose behaviour is undefined?  Sometimes it
> matters: if there's enough code that's relying on the undefined
> behaviour.  In this case I doubt they'd care.

I believe that there is a significant amount of code that depends on the 
fact that the null pointer is unaccessible and crashes the program.

> > > An implementation with an O(1) implementation of size() would
> > > presumably also not crash at that point either.
> > True. But the compiler can't know that. The compiler only sees the
> > code, it doesn't know what it's supposed to do.
>
> The standard library is part of the language specification, so the
> compiler is allowed to know about it.  An implementation might use an
> O(n) size() for unoptimized builds and an O(1) implementation when
> optimizing.  (I doubt there's any reason to do that, but I don't think
> it would be forbidden.)

True. I think there is a reasonable case in favor of optimizing size() 
== 0 in this manner. But, given that empty() exists, and given that it 
is potentially behavior-changing, I would probably go for other 
optimizations first.

Cheers,

-- Ulf