Re: Clean ways to count remove_if() removals?
On Jun 24, 10:33 am, Maxim Yegorushkin <maxim.yegorush...@gmail.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.
Well, here is stlport4 std::list<>::size() (bundled with Sun
Studio 12):
size_type size() const {
size_type __result = distance(begin(), end());
return __result;
}
The STL port is hardly a reference.
In this case: the STL port is based on the SGI implemenation.
And the SGI implementation clearly offers a different set of
guarantees than the standard---in the SGI documentation, size()
is O(n), and list<>::splice() is required to be constant in all
cases. The standard allows list<>::splice() to be linear when
it is necessary to recalculate the size, but says that size()
should be constant. (Of course, as Pete has pointed out, in the
standard, "should" is not the same thing as "shall".)
--
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