Re: Clean ways to count remove_if() removals?
On Jun 24, 2:00 pm, Pete Becker <p...@versatilecoding.com> wrote:
James Kanze wrote:
On Jun 23, 7:19 pm, Victor Bazarov <v.Abaza...@comAcast.net> wrote:
Marcel M=FCller wrote:
Victor Bazarov wrote:
How about
auto szBefore = my_list.size();
remove_if ...
auto szAfter = my_list.size();
If list is what it looks like, .size() is O(n). This might
be not intended.
Counting how many times the predicate is called is also O(n).
And the list *could* cache the size somewhere (if it's smart,
that is).
The standard requires list<>::size() to have constant time,
which means that it must be cached.
The standard says it "should have constant complexity". That's a
recommendation, not a requirement.
Ah, yes. Should, instead of shall. (But without some
qualifier, I don't see the point of the text.)
One issue here is the requirement that list::splice have
constant complexity, which can't be done if size is also
constant complexity.
I know there had been a lot of discussion about this; that's why
I actually looked it up in my copy of C++03. There, for the one
the one case of splice where it is relevant, the complexity is
given as "Constant time if &x == this; otherwise, linear time."
That sounded to me as if the issue had been resolved, in favor
of requiring size() to have constant complexity.
Interestingly, the SGI documentation says the opposite: size()
is linear, and all of the splice() functions are of constant
complexity, always. I suspect (but I don't know) that the SGI
documentation actually reflects the original, pre-standard STL
more closely. Which again suggests that the committee
"resolved" the issue in favor of requiring size() to have
constant complexity, rather than splice.
The issue is further clouded by the fact that in the standard,
complexity doesn't refer to time, but to a number of specific
operations, and the standard neglects to specify which
operations are being considered in the case of size() or
splice(). Even in the case where splice (or size()) is O(n), I
would expect zero calls to the copy constructor, or anything
else which might be expensive. (If the current wording in the
standard is maintained, and splice is allowed to be O(n), it
might be nice to specify that no calls to the copy constructor
or destructor. Perhaps at the top of the subsection on splice,
since this is really the whole point of the function. One could
argue that the name of the function already says this, but given
the semantics of functions like std::remove, it's hard to argue
anything based on the name.)
--
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