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

[Bruce Stephens]

Markus Wanner <address@hidden> writes:

> Zack Weinberg wrote:
>> Sure, but C++98 requires size() to be O(1) for every container, so
>> there's really no excuse for a 4-15% performance difference.
>
> Hm.. I didn't know that, thanks.

Just because the standard says that doesn't mean that it's so in
implementations, of course.  For example size() in SGI's list may be
linear: <http://www.sgi.com/tech/stl/List.html>.

The standard uses odd terminology (I think, anyway).  There's a table
in 23.1 showing the operations and complexities, and some of the
complexities are "constant", and some are "(Note A)".  This is
explained below the table: "Those entries marked ‘‘(Note A)’’ should
have constant complexity."

I wonder if that's an RFC-style "should"?

I don't have a more recent standard---perhaps this has changed?