Deleting items from std::map in a loop

[Tim Conkling]

Ok, so if I want to selectively delete items from a sequence like a
deque or vector from a for loop, I have to do something like this:

for(iter = list.begin(); iter != list.end(); ++iter)
{
if(shouldDelete (*iter))
{
iter = list.erase(iter );
--iter;
}
}

I'm trying to accomplish the same sort of thing in a map traversal.
Map's implementation of erase() doesn't return an iterator. How do I
accomplish what I'm trying to do?

Thanks,
Tim

[NFish]

Re: Deleting items from std::map in a loop

Tim Conkling wrote:
[color=blue]
> Ok, so if I want to selectively delete items from a sequence like a
> deque or vector from a for loop, I have to do something like this:
>
> for(iter = list.begin(); iter != list.end(); ++iter)
> {
> if(shouldDelete (*iter))
> {
> iter = list.erase(iter );
> --iter;
> }
> }
>
> I'm trying to accomplish the same sort of thing in a map traversal.
> Map's implementation of erase() doesn't return an iterator. How do I
> accomplish what I'm trying to do?
>
> Thanks,
> Tim
>[/color]

How about remove_if() ?

[Rob Williscroft]

Re: Deleting items from std::map in a loop

Tim Conkling wrote in news:bocpuq$ji2 $1@saturn.servi ces.brown.edu:
[color=blue]
> Ok, so if I want to selectively delete items from a sequence like a
> deque or vector from a for loop, I have to do something like this:
>
> for(iter = list.begin(); iter != list.end(); ++iter)
> {
> if(shouldDelete (*iter))
> {
> iter = list.erase(iter );
> --iter;
> }
> }
>
> I'm trying to accomplish the same sort of thing in a map traversal.
> Map's implementation of erase() doesn't return an iterator. How do I
> accomplish what I'm trying to do?
>[/color]

cont_type::iter ator iter = cont.begin(), lim = cont.end();
while ( iter != lim )
{
if( shouldDelete(*i ter))
{
list.erase( iter++ );
}
else ++iter;
}

It should work for any container, even ones where you can't
do --cont.end().

Rob.
--

http://www.victim-prime.dsl.pipex.com/

[tom_usenet]

Re: Deleting items from std::map in a loop

On Thu, 06 Nov 2003 06:44:55 GMT, NFish <nobody@nowhere .net> wrote:
[color=blue]
>Tim Conkling wrote:
>[color=green]
>> Ok, so if I want to selectively delete items from a sequence like a
>> deque or vector from a for loop, I have to do something like this:
>>
>> for(iter = list.begin(); iter != list.end(); ++iter)
>> {
>> if(shouldDelete (*iter))
>> {
>> iter = list.erase(iter );
>> --iter;
>> }
>> }
>>
>> I'm trying to accomplish the same sort of thing in a map traversal.
>> Map's implementation of erase() doesn't return an iterator. How do I
>> accomplish what I'm trying to do?
>>
>> Thanks,
>> Tim
>>[/color]
>
>How about remove_if() ?[/color]

Mutating algorithms don't work on set or map, that have const value
types.

Tom

[Ivan Vecerina]

Re: Deleting items from std::map in a loop

"Tim Conkling" <tconkling@brow n.edu> wrote in message
news:bocpuq$ji2 $1@saturn.servi ces.brown.edu.. .
| Ok, so if I want to selectively delete items from a sequence like a
| deque or vector from a for loop, I have to do something like this:
|
| for(iter = list.begin(); iter != list.end(); ++iter)
| {
| if(shouldDelete (*iter))
| {
| iter = list.erase(iter );
| --iter;
| }
| }

Yes, but for std::deque and std::vector at least, it would be
much more efficient to use the std::remove_if algorithm:
list.erase( remove_if( list.begin(), list.end(), &shouldDelet e )
, list.end() );

| I'm trying to accomplish the same sort of thing in a map traversal.
| Map's implementation of erase() doesn't return an iterator. How do I
| accomplish what I'm trying to do?

For information, see:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#130

So this is a debated issue. Note that some implementations of
map::erase do return an interator. But it is quite easy to
work around this limitation: just use the postfix ++ operator.

The following will do:

for(iter = map.begin() ; iter != map.end() ; )
{
if(shouldDelete (*iter))
map.erase( iter++ );
else
++iter;
}

The map.erase( iter++ ) line is equivalent to:
{
IterType kill = iter;
++iter;
map.erase(kill) ;
}
(the 1-line form works because the postfix++ operator
modifies the iter variable and returns its previous
value *prior* to the call of the erase function ).

I hope this helps,
Ivan
--

http://ivan.vecerina.com

[Howard Hinnant]

Re: Deleting items from std::map in a loop

In article <boe0h1$hc0$1@n ewshispeed.ch>,
"Ivan Vecerina" <please_use_web _form@ivan.vece rina.com> wrote:
[color=blue]
> For information, see:
> http://anubis.dkuug.dk/jtc1/sc22/wg2...losed.html#130
> So this is a debated issue. Note that some implementations of
> map::erase do return an interator.[/color]

Fwiw, lwg #130 has now been reopened. See especially the note:
[color=blue]
> A future standard may wish to reconsider this issue.[/color]

"The future is now" is the current feeling in the lwg.

-Howard

[Andrey Tarasevich]

Re: Deleting items from std::map in a loop

Tim Conkling wrote:
[color=blue]
> Ok, so if I want to selectively delete items from a sequence like a
> deque or vector from a for loop, I have to do something like this:
>
> for(iter = list.begin(); iter != list.end(); ++iter)
> {
> if(shouldDelete (*iter))
> {
> iter = list.erase(iter );
> --iter;
> }
> }[/color]

Now, think what's going to happen if 'shouldDelete' returns 'true' for
the very first element of the sequence...

The better way to do it would be

for(iter = list.begin(); iter != list.end();)
if(shouldDelete (*iter))
iter = list.erase(iter );
else
++iter;

or simply

list.erase(std: :remove_if(list .begin(), list.end(), shouldDelete),
list_end());

These two techniques are also applicable to 'std::vector'.
[color=blue]
> I'm trying to accomplish the same sort of thing in a map traversal.
> Map's implementation of erase() doesn't return an iterator. How do I
> accomplish what I'm trying to do?[/color]

The truth is that 'erase' in associative containers doesn't invalidate
any iterators except those that point to elements being erased (that's
also true for 'sid::list'). For this reason, you don't really need
'map::erase' to return an iterator. Just do this

for(iter = map.begin(); iter != map.end();)
if(shouldDelete (*iter))
map.erase(iter+ +);
else
++iter;

This will also work for 'std::list', but won't work for 'std::vector'.

--
Best regards,
Andrey Tarasevich