Re: STL map erase() functions question
Mark P <usenet@fall2005REMOVE.fastmailCAPS.fm> wrote:
olanglois@sympatico.ca wrote:
Hi,
I was asking myself to following question. What is better to erase an
element from a STL map:
calling (option #1)
size_type erase(const key_type& k)
or calling (option #2)
iterator find(const key_type& k) followed by
void erase(iterator pos) ?
I have looked into the STL implementation source code that I am using
and in the first case when calling size_type erase(const key_type& k)
in VC++.NET2003, the following happens:
It calls
equal_range()
which calls lower_bound() and upper_bound()
then compute the distance between iterators returned by equal_range()
then calls void erase(iterator first, iterator last)
which finally calls void erase(iterator pos)
In the second case, find() just calls lower_bound().
From my small investigation, it seems that, at least with VC++.NET2003
STL, using option #2 is more efficient. Is this just an implementation
artifact and with other STL implementations, option #1 might be better?
Why someone would want to use option #1 except maybe for saving some
typing?
Interesting points. My version of gcc (3.3.3) is implemented
essentially as you describe above and I had not noticed this until now.
This implementation appears to impose an efficiency penalty when the
intention is to erase at most a single object, as would almost always be
the case with a set or a map. But I think it's the "almost" which dooms
us here. One could define a peculiar less than function where, for
example, a certain special object compares equal to all other objects.
If that special object were the argument of erase(const key_type&) then
it would be necessary to erase a range of objects in the set or map
(notwithstanding that no pair of the objects *within* the set compares
equal). This special case then requires the equal_range query, or its
equivalent.
Quoting the oct 19 2005 draft of the corrected standard.
25.3 para 4 of that draft says
<auote>
The term strict refers to the requirement of an irreflexive relation
(!comp (x, x) for all x), and the term weak to
requirements that are not as strong as those for a total ordering, but
stronger than those for a partial ordering. If we
define equiv(a, b) as !comp (a, b) && !comp (b, a), then the
requirements are that comp and equiv both be
transitive relations:
- comp (a, b) && comp (b, c) implies comp (a, c)
- equiv(a, b) && equiv(b, c) implies equiv(a, c) [ Note: Under these
conditions, it can be shown that
- equiv is an equivalence relation
- comp induces a well-defined relation on the equivalence classes
determined by equiv
- The induced relation is a strict total ordering. - end note ]
</quote>
now the key_types compare function must induce a wtrict weak ordering on
the type key_type.
if there exists an S such that for any x equiv(x,S)==true and
equiv(S,x)==true. theen for any key_tyopes a,b
equiv(a,S) ==true and equiv(S,true) would then imply equiv(a,b)=true.
There is at most one entry in the map. with the special object theory.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]