Stuck in inf loop in a multimap iterator?

Hi,
While iterating through a multimap, I need to replace elements that meet
certain conditions with a new element.

There doesm't seem to be a replace() function for multimaps, so I'm
inserting a new element, and then deleting the old.

typedef multimap<double, MyStructType, greater<double> >;MyMultimap

MyMultimap map = ...

MyMultimap::iterator iter;

for(iter = map.begin(); iter!= map.end())
{
if(...)
{
map.insert(MyMultimap::value_type(newKey, newData));
map.erase(iter++);
}
else
++iter;
}

The for loop never exits.
I'm guessing that the iterator is messed up after the insert, but can't
see how to correct it.

Is there a way around this, or even a more efficient way to replace
elements altogether?

Thanks

Steve

re: Stuck in inf loop in a multimap iterator?

Steve Edwards wrote:[color=blue]
> Hi,
> While iterating through a multimap, I need to replace elements that meet
> certain conditions with a new element.
>
> There doesm't seem to be a replace() function for multimaps, so I'm
> inserting a new element, and then deleting the old.
>
> typedef multimap<double, MyStructType, greater<double> >;MyMultimap
>
> MyMultimap map = ...
>
> MyMultimap::iterator iter;
>
> for(iter = map.begin(); iter!= map.end())
> {
> if(...)
> {
> map.insert(MyMultimap::value_type(newKey, newData));
> map.erase(iter++);
> }
> else
> ++iter;
> }
>
> The for loop never exits.
> I'm guessing that the iterator is messed up after the insert, but can't
> see how to correct it.[/color]

Only the iterator to the deleted elemented becomes invalid. Other
iterators are not affected.

It looks like when you insert a new element it gets inserted after
iter. On a next iteration if(your new element) yields true and you
insert another element after it. That's how you probably get your
endless loop.
[color=blue]
> Is there a way around this, or even a more efficient way to replace
> elements altogether?[/color]

Build a new map rather modifying an existing one and then swap the
maps. Or try boost::multi_index.

re: Stuck in inf loop in a multimap iterator?

Erase returns the next iterator. So, iter = map.erase(iter) should
work.

re: Stuck in inf loop in a multimap iterator?

Balaji wrote:[color=blue]
> Erase returns the next iterator. So, iter = map.erase(iter) should
> work.[/color]

There is no difference between:

iter = map.erase(iter);

and

map.erase(iter++);

re: Stuck in inf loop in a multimap iterator?

map.erase(iter++)

Here, we erase what iter points to. This could invalidate iter. We then
try to increment a invalid iter.

iter = map.erase(iter)

Here, erase returns us the right next iterator.

Maxim, am I missing something?

re: Stuck in inf loop in a multimap iterator?

Balaji wrote:[color=blue]
> map.erase(iter++)
>
> Here, we erase what iter points to. This could invalidate iter. We then
> try to increment a invalid iter.[/color]

Wrong. Note the postfix increment, we increment first, then pass an old
copy to erase().
[color=blue]
> iter = map.erase(iter)
>
> Here, erase returns us the right next iterator.
>
> Maxim, am I missing something?[/color]

Also note that the standard (multi)map::erase does not return an
iterator. This is a non-standard extension.

re: Stuck in inf loop in a multimap iterator?

Balaji wrote:[color=blue]
> map.erase(iter++)
>
> Here, we erase what iter points to. This could invalidate iter.[/color]

This could invalidate the pointer passed to 'map.erase()' which is,
however, a different one than 'iter'! 'iter++' moves to the next
position and then returns the original iterator. This returned
iterator is passed to 'erase()' and invalidated.
[color=blue]
> We then try to increment a invalid iter.[/color]

Nope, we don't.
[color=blue]
> iter = map.erase(iter)
>
> Here, erase returns us the right next iterator.
>
> Maxim, am I missing something?[/color]

Apparently you missed the use of 'operator++(int)' on the argument
to 'erase()' - or you missed how post increment works for iterators.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence

re: Stuck in inf loop in a multimap iterator?

In article <1142342277.125189.98450@i40g2000cwc.googlegroups. com>,
"Maxim Yegorushkin" <maxim.yegorushkin@gmail.com> wrote:
[color=blue]
> Balaji wrote:[color=green]
> > Erase returns the next iterator. So, iter = map.erase(iter) should
> > work.[/color]
>
> There is no difference between:
>
> iter = map.erase(iter);
>
> and
>
> map.erase(iter++);[/color]

Thanks, rebuilding the map worked best.

Steve

re: Stuck in inf loop in a multimap iterator?

You could use one of the several variants of the std::replace algorithm.

A