Re: Re: using empty() instead of size()

Bruce Stephens wrote:
> Ulf Ochsenfahrt <ulf <at> ofahrt.de> 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