Deleting items from std::map in a loop

N

NFish

Tim said:
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

How about remove_if() ?
 
T

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
 
R

Rob Williscroft

Tim Conkling wrote in
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?

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

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

Rob.
 
I

Ivan Vecerina

| 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(), &shouldDelete )
, 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
 
A

Andrey Tarasevich

Tim said:
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;
}
}

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'.
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?

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'.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top