Re: Clean ways to count remove_if() removals?
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". 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.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34