473,320 Members | 1,600 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

STL map erase() functions question

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

Jul 1 '06 #1
8 6142
olangl...@sympatico.ca wrote:
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! ]

Jul 1 '06 #2
<ol*******@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 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! ]

Jul 1 '06 #3
ol*******@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! ]

Jul 1 '06 #4
>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! ]

Jul 2 '06 #5
Carl Barron wrote:
<ol*******@sympatico.cawrote:
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, <mapheader 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! ]

Jul 2 '06 #6
ol*******@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)
Ditto for Visual Studio 2005.
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?
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! ]

Jul 2 '06 #7
Mark P <us****@fall2005REMOVE.fastmailCAPS.fmwrote:
ol*******@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! ]

Jul 2 '06 #8
Hi Greg,
>
The original post describes the erase routine for a std::multimap
(which is defined in the same, <mapheader 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! ]

Jul 2 '06 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: s | last post by:
Here is a snippet of my code: <code> list< MyClass * >outgoing_pool; MyClass* GetWaitingObject(string freq) { MyClass *temp_ptr = NULL; list<MyClass*>::iterator i;
5
by: Angus Leeming | last post by:
Dinkumware's online STL reference http://tinyurl.com/3es52 declares std::map's overloaded erase member functions to have the interface: map::erase iterator erase(iterator where); iterator...
7
by: jose luis fernandez diaz | last post by:
Hi, Is this right any stl container (vector, deque, list, . . .)? typedef vector container; int main() { container<int> c1;
26
by: Pieter Thysebaert | last post by:
Hello, I've got a question conerning erasing key-value pairs from a std::map while iterating over it. According to the STL docs, erasing an element in a map invalidates all iterators pointing...
9
by: Amadeus W. M. | last post by:
I have a vector from which I want to erase elements between iterators i,j. If i<j, everything works as expected, but if j>i, an insertion is actually performed. Example: vector<double> x(10);...
6
by: alon | last post by:
I got the following situation: I have a few lists of integers, and I have an iterator pointing to one of the elements. I don't have a pointer to the list itself ! All I want is to remove the...
4
by: sks | last post by:
I have a question regarding std::multimap/iterators. At the SGI website, it says "Erasing an element from a multimap also does not invalidate any iterators, except, of course, for iterators that...
5
by: Anil | last post by:
I am facing problem while erasing an elemet from stl vector when its size is 2. It works fine when SIZE 2. Can anybody help me in this?? Following is the sample code which i tried. #include...
5
by: Boltar | last post by:
Hi Is there a way of inserting and erasing to/from a vector using an array index instead of an iterator or alternatively a way to map an index number to an iterator? eg: vector<intv;
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.