Re: STL map erase() functions question
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.
Perhaps this could be implemented more quickly as a lower_bound followed
by forward iteration to determine the upper_bound, but I don't think
this is generally true (consider a costly comparison function and a
large range to erase) so the given implementation seems reasonable, at
least (especially since map and set usually share an implementation with
their "multi" cousins).
So then, to answer your concluding question (or at least, weigh in with
my opinion thereupon) option #2 is probably more efficient when erasing
at most one element (bearing in mind that you need to check that the
iterator returned by find is dereferenceable). However option #1, in
addition to saving typing, also supports the more general case where 'k'
compares equal to multiple elements of the container. I imagine that
this "general case" is very rare for set or map so it probably makes
sense to keep option #2 in mind if performance is critical.
-Mark
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]