STL map erase() functions question

[olanglois]

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?

Thank you,
Olivier Langlois
http://www.olivierlanglois.net


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[Luke Meyers]

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) ?

The first, because it's shorter and more explicit about your intent.
If you mean to ask which is faster, I'd say the standard makes no
distinction and the answer will vary by particular implementation. If
you mean to ask which is *typically* faster, see below.

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?

I can't speak (at least not politely) as to the quality if your
implementation, but consider the following. If option #2 was really
more efficient than option #1, and they are equivalent in behavior, why
would a sane library implementor not simply implement option #1 as a
wrapper around option #2?

Luke


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[Mark P]

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().

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! ]

 

[Carl Barron]

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 know your [i think] lib provider is in this group often.
looks like an oversight that there is at most one item of a given
key_type in a map. seems the equivalent of
size_t erase(key_type const &x)
{
iterator it = find(x);
size_t out = it != end();
erase(it);
return out;
}
is an easy implementation. What am I missing? The implemetor can use
the inards of map to get this at least as efficient as this.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[benben]

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?

Can't give you a definitive answer but if Opt1 can be implemented in
terms of Opt2 trivially and more efficiently why would the library
developer go all the length to avoid that implementation?

Thank you,
Olivier Langlois
http://www.olivierlanglois.net

Regards,
Ben

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[Jeffrey Schwab]

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)

Ditto for Visual Studio 2005.

In the second case, find() just calls lower_bound().

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?

For the same reason the vendor used this implementation in the first
place: To minimize the quantity of code that needs to be maintained.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[Greg Herlihy]

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 know your [i think] lib provider is in this group often.
looks like an oversight that there is at most one item of a given
key_type in a map. seems the equivalent of
size_t erase(key_type const &x)
{
iterator it = find(x);
size_t out = it != end();
erase(it);
return out;
}

The above implementation potentially calls erase(end()) which is not a
well-defined operation upon a std::map. (Note that since erase(end(),
end()) is a well-defined operation, replacing erase(it) with erase(it,
it) would be one way to fix the problem.)

The original post describes the erase routine for a std::multimap
(which is defined in the same, <map> header file), so it's likely a
simple mix-up.

Greg


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[Carl Barron]

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! ]

 

[olanglois]

Hi Greg,

The original post describes the erase routine for a std::multimap
(which is defined in the same, <map> header file), so it's likely a
simple mix-up.

For your information, I did not mixed-up map::erase with
multimap::erase. To clarify this point, map::erase in VC++.NET is
defined in its base class xtree which is also the base class for
multimap. So the same erase function is used for both map and multimap
but what I described in the original post about map::erase is exact.

Greetings,
Olivier Langlois
http://www.olivierlanglois.net


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]