Re: Clean ways to count remove_if() removals?
* James Kanze:
On Jun 24, 6:08 pm, "Alf P. Steinbach" <al...@start.no> wrote:
* joseph cook:
On Jun 24, 3:30 am, James Kanze <james.ka...@gmail.com> wrote:
The standard requires list<>::size() to have constant time,
which means that it must be cached.
So it does.
It doesn't.
There are two possible in practice list implementations: one
where size is O(1), and one where splicing is O(1).
The standard allows both.
That depends on how you interpret the "should".
That's simple. Where constant time is a requirement that table just says
"constant". But in cases where that might not be practically achievable in all
cases, it says "Note A", which says "should", i.e. it's not required.
Formally, yes,
it allows both. But the intent is clear: size() should be
constant, and splice has linear complexity in the cases where
this would be necessary to update size().
The documentation for SGI STL states that it can be O(N),
and warns that one should always use "empty()" instead of "size()
==0". I wonder why that is...
In order to make splicing O(1).
The SGI documentation requires splice() to be O(1), in all
cases, and says that size() is O(n). This is in direct
contradiction with the standard. The SGI documentation is, I
believe, pre-standard, which suggests that the standards
committee made an intentional change here, which is, in itself,
significant.
See my posting else-thread: I think SGI and original STL had it right, and the
standard has it wrong, with respect to usefulness/practicality. I used to have
Stepanov's STL spec. But I had a disk crash which selectively removed whole
directories and one time before a very similar thing made files with a certain
/name pattern/ unreadable (I guess there's something physically wrong, but
mostly it's the darned driver software and caching that messes it up, and then
confuses Windows, which goes on rampant kill! delete! spree).
- Alf
--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! :-) Just going there is good. Linking
to it is even better! Thanks in advance!