Erase in a map

[Charles Zhang]

I want to erase items in a map based on some criteria. However, as soon
as the erase is called, iterator become invalid. I would like someone
to tell me the better way to do it.

Here is the source code I am using, and it is crashing.

for ( pos = connectionMap.begin(); pos != connectionMap.end(); ++pos){
ConnectionInfo* conn = pos->second;

if ( current - conn->lastRequestTime > 60 * timeOut ) {
connectionMap.erase(pos);
}
}

To overcome the problem, I start the loop from the beginning after a
item is removed. But this is too slow.

Thanks

Charles Zhang

[aao]

   for ( pos = connectionMap.begin(); pos != connectionMap.end(); ){

         ConnectionInfo* conn = pos->second;
 
         if ( current - conn->lastRequestTime > 60 * timeOut ) {

                pos  =  connectionMap.erase(pos);
         }

        else

            ++pos;

    }
 

 

"Charles Zhang" <Charle...@newsgroups.nospam> wrote in message news:%23Rp6mF$ZHHA...@TK2MSFTNGP05.phx.gbl...

[Charles Zhang]

Thank you very much. Your solution works just fine.

Book <<The C++ Standard Library>> written by Nicolai M. Josuttis says
"erase returns nothing". The incorrect statement led to a wrong direction.

Thanks again.

Charles Zhang

aao wrote:
> for ( pos = connectionMap.begin(); pos != connectionMap.end(); ){
> ConnectionInfo* conn = pos->second;
>
> if ( current - conn->lastRequestTime > 60 * timeOut ) {

> * pos =* connectionMap.erase(pos);
> }
> else
> * ++pos;*
>
> }
>
>
> "Charles Zhang" <Charle...@newsgroups.nospam
> <mailto:Charle...@newsgroups.nospam>> wrote in message

[Igor Tandetnik]

"Charles Zhang" <Charle...@newsgroups.nospam> wrote in message
news:O24eXUGa...@TK2MSFTNGP05.phx.gbl

> Thank you very much. Your solution works just fine.
>
> Book <<The C++ Standard Library>> written by Nicolai M. Josuttis says
> "erase returns nothing". The incorrect statement led to a wrong
> direction.

According to the standard, map::erase does return nothing, whereas, say,
vector::erase returns the iterator to the next element after the one
being erased. This is an oversight that will likely be fixed in the next
version of the standard, so that the method signature is uniform across
all containers. The STL implementation shipped with VC has map::erase
returning an iterator as a conforming extension, in anticipation of this
change in the standard.

If you want your code to be standard conforming and portable now,
replace

pos = connectionMap.erase(pos);

with

connectionMap.erase(pos++); // must use post-increment

This works with maps (as well as sets, lists and so on) since map::erase
doesn't invalidate any iterators except those referring to the element
being erased. vector::erase (and deque) on the other hand invalidates
all iterators to the erased element and all following elements, so one
has to use the first version with these containers (luckily, their
erase() method does return an iterator).
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

[freak]

On Mar 16, 9:35 pm, Charles Zhang <CharlesZh...@newsgroups.nospam>
wrote:

use standard library:
#include <algorithm>

/*assuming that TConnectionMap implements std::map<long,ConnectionInfo
*> */

typedef std::map<long,ConnectionInfo *> TConnectionMap;

struct ConnExpired{//define a predicate class;

ConnExpired(const long cur): current(cur) {};

bool operator () (const TConnectionMap::value_type& conn)
const
{
return current - conn.second->lastRequestTime > 60 *
timeOut ;
};

private:
const long current;
};

{//somewhere in the code:
TConnectionMap connectionMap;
long current;
std::remove_if
(connectionMap.begin(),connectionMap.end(),ConnExpired(current));
};

and do not worry about the validity of the iterators because the
STL(standard template library) is responsible for it.

[freak]

> STL(standard template library) is responsible for it.- Hide quoted text -
>
> - Show quoted text -

PS:on my last post the 'std::remove_if' function returns a valid
iterator to the end of the range.

[Igor Tandetnik]

"freak" <farid....@gmail.com> wrote in message
news:1174297401.4...@b75g2000hsg.googlegroups.com

> On Mar 16, 9:35 pm, Charles Zhang <CharlesZh...@newsgroups.nospam>
> wrote:
>> I want to erase items in a map based on some criteria.
>

> use standard library:
>
> std::remove_if
> (connectionMap.begin(),connectionMap.end(),ConnExpired(current));

remove_if won't work on a map. It requires that elements of a container
be assignable, and map's elements aren't. Try it, it won't compile.

[freak]

On Mar 19, 3:09 pm, "Igor Tandetnik" <itandet...@mvps.org> wrote:
> "freak" <farid.mehr...@gmail.com> wrote in message

>
> news:1174297401.4...@b75g2000hsg.googlegroups.com
>
> > On Mar 16, 9:35 pm, Charles Zhang <CharlesZh...@newsgroups.nospam>
> > wrote:
> >> I want to erase items in a map based on some criteria.
>
> > use standard library:
>
> > std::remove_if
> > (connectionMap.begin(),connectionMap.end(),ConnExpired(current));
>
> remove_if won't work on a map. It requires that elements of a container
> be assignable, and map's elements aren't. Try it, it won't compile.
> --
> With best wishes,
> Igor Tandetnik
>

I did and got nervous a bit.Looks like we have to write the code
manually.But I do not see any reason for assifnability.Maybe remove_if
needs to be changed to what we did here?

[aao]

I know that works with gcc and intel compilers on Linux, and I beleave that
signature should(will) be in the standard in next update.

[Igor Tandetnik]

freak <farid....@gmail.com> wrote:
> I did and got nervous a bit.Looks like we have to write the code
> manually.But I do not see any reason for assifnability.Maybe remove_if
> needs to be changed to what we did here?

Note that remove_if takes as parameters a pair of iterators, but not the
container these iterators came from (if any). "What we did here"
requires calling erase() method on a container, which remove_if doesn't
have access to.

Further note that the algorithm using erase() would be O(N^2) when
applied to vector or deque, whereas existing remove_if implementation is
O(N).

--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not

[Ulrich Eckhardt]

The typically used solution is this:

while(it!=end)
if(predicate(*it))
container.erase(it++);
else
++it;

Note the use of postfix and prefix increment.

Uli

[Norbert Unterberg]

Ulrich Eckhardt schrieb:

> The typically used solution is this:
>
> while(it!=end)
> if(predicate(*it))
> container.erase(it++);

erase() returns an iterator of the element after the erased ones.
So you can write:

if(predicate(*it))
it = container.erase(it);
else
++it;

Norbert

[Ulrich Eckhardt]

Norbert Unterberg wrote:
> Ulrich Eckhardt schrieb:
>
>> The typically used solution is this:
>>
>> while(it!=end)
>> if(predicate(*it))
>> container.erase(it++);
>
> erase() returns an iterator of the element after the erased ones.

According to my pre-release copy of the standard, that is a requirement for
containers that model the sequence requirement. However, that same copy
mandates a void returntype for erase(iterator) of [multi](set|map), and
that is effectively what is done by several implementations of the
standardlibrary. I believe that the Dinkumware library returns iterators as
an extension or for backward compatibility with the STL.

Uli

[Tom Widmer [VC++ MVP]]

The current C++0x working paper has modified associative containers to
do what sequence containers do, returning the next iterator for erase,
so it's becoming increasingly safe to rely on this.

Tom

[Stephen Howe]

> I believe that the Dinkumware library returns iterators as
> an extension or for backward compatibility with the STL.

The other way round.
It is forward compatibility with the intended next C++ standard.

Stephen Howe

[P.J. Plauger]

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:uuQurQCj...@TK2MSFTNGP05.phx.gbl...

Both, actually. An interim draft of STL had erase return iterators
in all cases, but it disappeared somewhere along the way. We left
it in for early customers at first, then kept it in when it was
clear that the revised C++ Standard would restore this very useful
behavior.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

[@hotmail.com Steev]

"P.J. Plauger" <p...@dinkumware.com> wrote in message
news:peWdnXlrK-10Barb...@giganews.com...

Yay! that makes me happy!