Style Question: erasing map element in for loop

[Jim Langston]

There's the thing about iterating though a map or vector when you may delete
one of the elements, where you simply assign the iterator to the map.erase()
statement or increment it if you don't. Well, I have this issue where I may
delete the map element in 3 different places:


for ( map_key_pcmissile::iterator mit = World.Missiles.begin(); mit !=
World.Missiles.end(); )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
else
{
if ( /* Some Condition */ )
{
for ( /* Iterate through vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
for ( /* Iterate through a different vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
}
++mit;
}
}

As you can see two of these are fairly heavily nested and so the ++mit; at
the end shouldn't occur if the map elements were deleted in any of the
above. Right now it's just checking one.

I'm wondering the best way to do this. The first obvious way is to simply
set some boolean flag if the element was deleted and only increment mit if
the flag is set to false. This is my usual solution in this type of
problem, but I don't tend to like it. It just seems not the Right Thing.
What would you do in this case? What is the Right Thing to do?

 

[benben]

There's the thing about iterating though a map or vector when you may delete
one of the elements, where you simply assign the iterator to the map.erase()
statement or increment it if you don't. Well, I have this issue where I may
delete the map element in 3 different places:


for ( map_key_pcmissile::iterator mit = World.Missiles.begin(); mit !=
World.Missiles.end(); )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
else
{
if ( /* Some Condition */ )
{
for ( /* Iterate through vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
for ( /* Iterate through a different vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
}
++mit;
}
}

As you can see two of these are fairly heavily nested and so the ++mit; at
the end shouldn't occur if the map elements were deleted in any of the
above. Right now it's just checking one.

I'm wondering the best way to do this. The first obvious way is to simply
set some boolean flag if the element was deleted and only increment mit if
the flag is set to false. This is my usual solution in this type of
problem, but I don't tend to like it. It just seems not the Right Thing.
What would you do in this case? What is the Right Thing to do?

What was std::remove_if() designed for? With little detail you gave us
that is the only advice i can give.

Ben

 

[Alf P. Steinbach]

* Jim Langston:

There's the thing about iterating though a map or vector when you may delete
one of the elements, where you simply assign the iterator to the map.erase()
statement or increment it if you don't. Well, I have this issue where I may
delete the map element in 3 different places:


for ( map_key_pcmissile::iterator mit = World.Missiles.begin(); mit !=
World.Missiles.end(); )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
else
{
if ( /* Some Condition */ )
{
for ( /* Iterate through vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
for ( /* Iterate through a different vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
}
++mit;
}
}

Unless the code checks for World.Missiles.end() in each of the last
cases, this code risk deleting its way right out of the map: there can
potentially be multiple deletes in each iteration of the outer loop.

As you can see two of these are fairly heavily nested and so the ++mit; at
the end shouldn't occur if the map elements were deleted in any of the
above. Right now it's just checking one.

I'm wondering the best way to do this. The first obvious way is to simply
set some boolean flag if the element was deleted and only increment mit if
the flag is set to false. This is my usual solution in this type of
problem, but I don't tend to like it. It just seems not the Right Thing.
What would you do in this case? What is the Right Thing to do?

A boolean flag is IMO the way to go if more than one delete can occur in
each outer loop iteration.

Otherwise there is the keyword 'continue'.

There's also 'return', like, for the single delete per iteration case,

bool eraseGoner(
map_key_pcmissile& map, map_key_pcmissile::iterator& it
)
{
// lots of stuff here, including
i = map.erase( i );
return true;
//
return false;
}


map_key_pcmissile::iterator mit = World.Missiles.begin();
while( mit != World.Missiles.end(); )
{
if( !eraseGoner( World.Missiles, mit ) ) { ++mit; }
}

 

[Jim Langston]

What was std::remove_if() designed for? With little detail you gave us
that is the only advice i can give.

std::remove_if() won't work because I need there are other situations where
I need to not delete an element, and also I have to do stuff with the
element before I delete it.

 

[Jim Langston]

* Jim Langston:

Unless the code checks for World.Missiles.end() in each of the last cases,
this code risk deleting its way right out of the map: there can
potentially be multiple deletes in each iteration of the outer loop.



A boolean flag is IMO the way to go if more than one delete can occur in
each outer loop iteration.

Actually, that is something I didn't state. If the element is deleted, it
needs to stop processing that element and go to the next iteration of the
out enclosing for loop. Of course the easiest way would be to have a goto
statement, but I just don't use goto's, even though some may argue this is a
case to use it, I still don't like it.

Otherwise there is the keyword 'continue'.

Yes, although continue only exits the smallest enclosing loop. I think I'll
need to set a flag and use continue twice.

There's also 'return', like, for the single delete per iteration case,

bool eraseGoner(
map_key_pcmissile& map, map_key_pcmissile::iterator& it
)
{
// lots of stuff here, including
i = map.erase( i );
return true;
//
return false;
}


map_key_pcmissile::iterator mit = World.Missiles.begin();
while( mit != World.Missiles.end(); )
{
if( !eraseGoner( World.Missiles, mit ) ) { ++mit; }
}

Yeah, I've considered how breaking this up into functions may help me, and
that may be what I'll need to do to make it easiest.

What this is actually for is a game server. The outer iterator is iterating
thorough beams (bullets if you will). The first if statement sees if the
bullet has gone out of range, if it has it deletes it. The first enclosed
for statement is iterating through the players. If the beam hits a player
then the server makes the player take damage, sends messages, etc... then
deletes the beam. The second iterator interates through NPCs doing the same
thing. Which is why the map element (the bullet) may be deleted in one of
three places.

 

[Colander]

If you don't like to use goto, use return...

outer:
while(foo)
while(bar)
if(answer == 42) goto outer;

becomes;

void makeReturnLikeContinueOuter()
{
while(foo)
while(bar)
if(answer == 42) return;
}

while(foo)
makeReturnLikeContinueOuter();


This is the only case so far I found the use of goto appropriate.

 

[Luke Meyers]

for ( map_key_pcmissile::iterator mit = World.Missiles.begin(); mit !=
World.Missiles.end(); )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
else
{
if ( /* Some Condition */ )
{
for ( /* Iterate through vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
for ( /* Iterate through a different vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
}
++mit;
}
}

Since is seems like you basically want to select a single action, which
is either "increment the iterator" or "do stuff and delete," why not
have a variable to represent that action? That variable will have only
one value, making the whole question of performing two incompatible
actions moot.

How about something like:

for (MapIterator mit = map.begin(), end = map.end(); mit != end; ++mit)
{
// Use a callable type which provides a hook for the
just-prior-to-delete behavior.
typedef SomeCallableType ElementFunctor;

// Choose one action to take -- either increment, or perform some
logic and delete.
ElementFunctor action = Increment;
if (cond1) action = new DeletionActionA;
else if (cond2) action = new DeletionActionB;

// After conditional logic,
action(mit);
}

Modify as necessary to suit your needs. For example, if you need to do
two deletion actions, but only actually delete once (obviously you
don't want to delete twice), you could use a chaining mechanism or some
such to combine the two actions. I'm sure you can sort out the
details.

Luke

 

[Jim Langston]

There's the thing about iterating though a map or vector when you may
delete one of the elements, where you simply assign the iterator to the
map.erase() statement or increment it if you don't. Well, I have this
issue where I may delete the map element in 3 different places:


for ( map_key_pcmissile::iterator mit = World.Missiles.begin(); mit !=
World.Missiles.end(); )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
else
{
if ( /* Some Condition */ )
{
for ( /* Iterate through vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
for ( /* Iterate through a different vector */ )
{
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/*** Do some stuff and delete map element here ***/
}
}
}
}
++mit;
}
}

As you can see two of these are fairly heavily nested and so the ++mit; at
the end shouldn't occur if the map elements were deleted in any of the
above. Right now it's just checking one.

I'm wondering the best way to do this. The first obvious way is to simply
set some boolean flag if the element was deleted and only increment mit if
the flag is set to false. This is my usual solution in this type of
problem, but I don't tend to like it. It just seems not the Right Thing.
What would you do in this case? What is the Right Thing to do?

What I finally settled on:

bool CheckIfPlayerHit( map_key_pcmissile::iterator& mit )
{
for ( /* Iterate though map */)
{
if ( /* Some Condition */ ) {
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/* do stuff */
World.Missiles.erase(mit);
return true;
}
}
}
return false;

}

bool CheckIfNPCHit( map_key_pcmissile::iterator& mit )
{
for ( /* Iterate though map */)
{
if ( /* Some Condition */ ) {
if ( /* Some Condition */ )
{
if ( /* Some Condition */ )
{
/* do stuff */
World.Missiles.erase(mit);
return true;
}
}
}
return false;
}

/* in main function (not main()) */
for ( map_key_pcmissile::iterator mit = World.Missiles.begin(); mit !=
World.Missiles.end(); )
{
if ( /* Some Condition */ )
{
mit = World.Missiles.erase(mit);
}
else
{
if ( /* Some Condition */ ) {
{
if ( CheckIfPlayerHit( mit ) )
continue;

if ( CheckIfNPCHit( mit ) )
continue;
}
++mit;
}
}

This does have the advantage of making my main function much clearer. I
think this is probably the best solution.

 

[Mark P]

There's the thing about iterating though a map or vector when you may delete
one of the elements, where you simply assign the iterator to the map.erase()
statement or increment it if you don't. Well, I have this issue where I may
delete the map element in 3 different places:

[code snipped]

As you can see two of these are fairly heavily nested and so the ++mit; at
the end shouldn't occur if the map elements were deleted in any of the
above. Right now it's just checking one.

I'm wondering the best way to do this. The first obvious way is to simply
set some boolean flag if the element was deleted and only increment mit if
the flag is set to false. This is my usual solution in this type of
problem, but I don't tend to like it. It just seems not the Right Thing.
What would you do in this case? What is the Right Thing to do?

How about...

typedef map_key_pcmissile::iterator mkpIt;

for (mkpIt mit = World.Missiles.begin(), nextIt = mit;
mit != World.Missiles.end();
mit = nextIt);
{
++(nextIt = mit);

// do stuff; don't worry about advancing mit
}

You could also integrate the ++(nextIt = mit) into the continuation
condition if you wanted.

-Mark