stl::list modified erase

[Philip Mueller]

Hi,

I am using multiple stl::list s of different types.

Now I want to write a function

list<type>::iterator s_erase(list<type> l, list<type>::iterator it)

that takes an iterator and deletes the element it is pointing add, and
returns the iterator pointing to the predecessor of the erased element.

like this:

return l.erase(it)--;

But I want this to work for any contained type. For clarification:
I have theses lists:

list<cShip> Ships;
list<cProjectile> Projectiles;
list<cAsteroid> Asteroids;

And I want my function to work on all of these lists. Is that possible?

Regards
Philip

 

[Christopher]

Hi,

I am using multiple stl::list s of different types.

Now I want to write a function

list<type>::iterator s_erase(list<type> l, list<type>::iterator it)

that takes an iterator and deletes the element it is pointing add, and
returns the iterator pointing to the predecessor of the erased element.

like this:

return l.erase(it)--;

But I want this to work for any contained type. For clarification:
I have theses lists:

list<cShip> Ships;
list<cProjectile> Projectiles;
list<cAsteroid> Asteroids;

And I want my function to work on all of these lists. Is that possible?

Regards
Philip

There already exists a method that does that: std::list::erase
It sounds to me that you are making a function that does not do
anything differently than the method that exists? Am I missing
something?

 

[Christopher]

There already exists a method that does that: std::list::erase
It sounds to me that you are making a function that does not do
anything differently than the method that exists? Am I missing
something?

Oh, I see the only difference is std::list::erase return an iterator
pointing to the element after the erased and you want it to point to
the element before.

Well, I see no reason you could not decrement the returned iterator,
as long as you check for the it = list.begin() case
Why even make a function for that? If you have the list handy, than
you have its type and can make an iterator, and call erase on it.

 

[Kai-Uwe Bux]

Hi,

I am using multiple stl::list s of different types.

Now I want to write a function

list<type>::iterator s_erase(list<type> l, list<type>::iterator it)

that takes an iterator and deletes the element it is pointing add, and
returns the iterator pointing to the predecessor of the erased element.

like this:

return l.erase(it)--;

But I want this to work for any contained type. For clarification:
I have theses lists:

list<cShip> Ships;
list<cProjectile> Projectiles;
list<cAsteroid> Asteroids;

And I want my function to work on all of these lists. Is that possible?

Sure. Define a function template:

template < typename ListType >
typename ListType::iterator
s_erase ( ListType & the_list,
typename ListType::iterator iter ) {
typename ListType::iterator result = the_list.erase( iter );

// make up your mind whether this indicates a bug in client code or
// requires an exception:
assert ( result != the_list.begin() );

-- result;
return ( result );
}


BTW: I think, such a function fills a much needed gap in your code base.


Best

Kai-Uwe Bux

 

[Philip Mueller]

Sure. Define a function template:

[...]
Thanks, that's just what I need. Unfortunately I have never worked with
templates in C and I just can't get the syntax for a call to that
function right. Could you give an example?

BTW: I think, such a function fills a much needed gap in your code base.

Yeah, it would really make the project look a whole lot cleaner

Regards
Philip

 

[Kai-Uwe Bux]

Sure. Define a function template:

[...]

Please, don't snip context that you are refering to:

template < typename ListType >
typename ListType::iterator
s_erase ( ListType & the_list,
typename ListType::iterator iter ) {
...
}

Thanks, that's just what I need. Unfortunately I have never worked with
templates in C and I just can't get the syntax for a call to that
function right. Could you give an example?

Since all types can be deduced from the arguments, the following should
suffice:

s_erase( my_list, my_iter );

Yeah, it would really make the project look a whole lot cleaner

Either you are great master of irony, or my hint was just too subtle.


Best

Kai-Uwe Bux

 

[Philip Mueller]

template < typename ListType >
typename ListType::iterator
s_erase ( ListType & the_list,
typename ListType::iterator iter ) {
...
}



Since all types can be deduced from the arguments, the following should
suffice:

s_erase( my_list, my_iter );

When I do this

list<int> Test;
list<int>::iterator iter;
iter = s_erase(Test, iter);

I get a compile error saying

undefined reference to `std::list<int, std::allocator<int> >::iterator
s_erase<std::list<int, std::allocator<int> > >(std::list<int,
std::allocator<int> >&, std::list<int, std::allocator<int> >::iterator)'

I find this very difficult to read, but even after reading it multiple
times I don't understand it.
Do you know where I can find introductory texts about templates?

Either you are great master of irony, or my hint was just too subtle.

Maybe it was.

For clarification:

I need s_erase because I have a for-loop iterating over the list and
deleting objects that satisfy a given condition.[1]
Now, when I use the stl::list "erase()" method, it returns an iterator
to the next element.
In the next iteration the loop also increments the iterator so I have
skipped the Element after the one I deleted.
If you have a different, simpler idea, you're welcome to share it with
me

Regards
Philip

[1]:
list<cShip> Ships;
for (list<cShip>::iterator iS = Ships.begin(); iS != Ships.end(); iS++)
{
//This is the version that skips elements. I don't want that
if (condition(iS))
iS = Ships.erase(iS);
}

Another possibility would be

if (condition(iS))
{
iS = Ships.erase(iS);
iS--;
}

but I don't think that's good code, especially because I need that
fragment at multiple locations in the program.
That's why I want a method for that.

if (condition(iS)) iS = s_erase(Ships, iS);

 

[Kai-Uwe Bux]

When I do this

list<int> Test;
list<int>::iterator iter;
iter = s_erase(Test, iter);

I get a compile error saying

undefined reference to `std::list<int, std::allocator<int> >::iterator
s_erase<std::list<int, std::allocator<int> > >(std::list<int,
std::allocator<int> >&, std::list<int, std::allocator<int> >::iterator)'

Did you put the declaration of s_erase in a header and the implementation in
a cpp-file? If so, you would need a compiler that implements the export
keyword. For compilers that don't (which is the case for most of them),
template implementations need to go into the header file.

I find this very difficult to read, but even after reading it multiple
times I don't understand it.
Do you know where I can find introductory texts about templates?

I use

Vandervoorde and Josuttis: "C++ Templates: The Complete Guide"

but I don't know if that qualifies as an introductory text.

Either you are great master of irony, or my hint was just too subtle.

Maybe it was.

For clarification:

I need s_erase because I have a for-loop iterating over the list and
deleting objects that satisfy a given condition.[1]
Now, when I use the stl::list "erase()" method, it returns an iterator
to the next element.
In the next iteration the loop also increments the iterator so I have
skipped the Element after the one I deleted.
If you have a different, simpler idea, you're welcome to share it with
me

The standard idioms to remove elements from a list is:

for ( iterator iter = my_list.begin(); iter != my_list.end(); ) {
if ( condition( *iter ) ) {
iter = my_list.erase( iter );
} else {
++ iter;
}
}

More concisely but requiring a function or function object you can use the
remove_if() member function:

my_list.remove_if( predicate_object );

Regards
Philip

[1]:
list<cShip> Ships;
for (list<cShip>::iterator iS = Ships.begin(); iS != Ships.end(); iS++)
{
//This is the version that skips elements. I don't want that
if (condition(iS))
iS = Ships.erase(iS);
}

Another possibility would be

if (condition(iS))
{
iS = Ships.erase(iS);
iS--;
}

but I don't think that's good code, especially because I need that
fragment at multiple locations in the program.
That's why I want a method for that.

if (condition(iS)) iS = s_erase(Ships, iS);

The problem with those alternative versions is that they have some trouble
deleting the first element of the list.


Best

Kai-Uwe Bux

 

[Daniel T.]

When I do this

list<int> Test;
list<int>::iterator iter;
iter = s_erase(Test, iter);

I get a compile error saying

undefined reference to `std::list<int, std::allocator<int> >::iterator
s_erase<std::list<int, std::allocator<int> > >(std::list<int,
std::allocator<int> >&, std::list<int, std::allocator<int> >::iterator)'

I find this very difficult to read, but even after reading it multiple
times I don't understand it.
Do you know where I can find introductory texts about templates?

My guess is it is complaining because you put the definition of the
function in a cpp file other than the one using it. Take the code that
Kai gave you and paste it directly in a .h file.

Either you are great master of irony, or my hint was just too subtle.

Maybe it was.

For clarification:

I need s_erase because I have a for-loop iterating over the list and
deleting objects that satisfy a given condition.[1]
Now, when I use the stl::list "erase()" method, it returns an iterator
to the next element.
In the next iteration the loop also increments the iterator so I have
skipped the Element after the one I deleted.
If you have a different, simpler idea, you're welcome to share it with
me

Ships.remove_if( &condition );

The above will do what you describe below without much effort on your
part. You might have to modify condition to take a const reference
rather than a pointer.

[1]:
list<cShip> Ships;
for (list<cShip>::iterator iS = Ships.begin(); iS != Ships.end(); )
{
if (condition(iS))
iS = Ships.erase(iS);

else
++iS;

}

I modified the code above so that it doesn't skip elements anymore.

 

[Victor Bazarov]

Hi,

I am using multiple stl::list s of different types.

Now I want to write a function

list<type>::iterator s_erase(list<type> l, list<type>::iterator it)

that takes an iterator and deletes the element it is pointing add, and
returns the iterator pointing to the predecessor of the erased
element.
like this:

return l.erase(it)--;

But I want this to work for any contained type. For clarification:
I have theses lists:

list<cShip> Ships;
list<cProjectile> Projectiles;
list<cAsteroid> Asteroids;

And I want my function to work on all of these lists. Is that
possible?

You need to work around the possibility of your 'l's being empty,
or containing only one element (after which you're trying to use
post-decrement on the 'end', which is UB), but beyond that, what
is stopping you from making it a template?

V

 

[Philip Mueller]

The standard idioms to remove elements from a list is:

for ( iterator iter = my_list.begin(); iter != my_list.end(); ) {
if ( condition( *iter ) ) {
iter = my_list.erase( iter );
} else {
++ iter;
}
}

First of all, thanks for your suggestions Kai-Uwe.
This example makes perfect sense to me. But I have problems adapting it
to a special case:

for (iProj = Projectiles.begin(); iProj != Projectiles.end(); iProj++)
for (iAst = Asteroids.begin(); iAst != Asteroids.end(); iAst++)
if (iProj->DistanceTo(&*iAst) <= iAst->getRadius())
{
iProj = Projectiles.erase(iProj);
iAst = Asteroids.erase(iAst);
}

What I mean to do here is test two list of objects for collisions
between an element from the "Projectiles" list and an element from the
"Asteroids" list (Collision detection via "DistanceTo").
Then if there is such a collision, I want to delete both the projectile
and the asteroid.

Can someone give me a hint?

Regards
Philip



p.s.:
My best try so far is

for (iProj = Projectiles.begin(); iProj != Projectiles.end()
{
iAst = Asteroids.begin();
while (iAst != Asteroids.end()
&& iProj->DistanceTo(&*iAst) > iAst->getRadius())
iAst++;
if (iAst != Asteroids.end())
{
iAst = Asteroids.erase(iAst);
iProj = Projectiles.erase(iProj);
}
else
iProj++;
}

There has to be a better way.

 

[Kai-Uwe Bux]

First of all, thanks for your suggestions Kai-Uwe.
This example makes perfect sense to me. But I have problems adapting it
to a special case:

for (iProj = Projectiles.begin(); iProj != Projectiles.end(); iProj++)
for (iAst = Asteroids.begin(); iAst != Asteroids.end(); iAst++)
if (iProj->DistanceTo(&*iAst) <= iAst->getRadius())
{
iProj = Projectiles.erase(iProj);
iAst = Asteroids.erase(iAst);
}

What I mean to do here is test two list of objects for collisions
between an element from the "Projectiles" list and an element from the
"Asteroids" list (Collision detection via "DistanceTo").
Then if there is such a collision, I want to delete both the projectile
and the asteroid.

Can someone give me a hint?

Would this work:

bool hits_asteroid ( Projectile const & p,
AsteroidList & Asteroids ) {
for ( AsteroidList::iterator iAst = Asteroids.begin();
iAst != Asteroids.end() ) {
if ( p.DistanceTo(&*iAst) <= iAst->getRadius() ) {
iAst = Asteroids.erase( iAst );
return ( true );
} else {
++iAst;
}
}
return ( false );
}

and then:

for ( iProj = Projectiles.begin(); iProj != Projectiles.end() ) {
if ( hits_asteroid( *iProj, Asteroids ) ) {
iProj = Projectiles.erase( iProj );
} else {
++ iProj;
}
}


If you want to fold that into a double loop (e.g., if you don't like
predicates with side effects), I would think that the best way is to have a
boolean flag that keeps track whether an explosion has happened.


Best

Kai-Uwe Bux

 

[Philip Mueller]

Would this work:

bool hits_asteroid ( Projectile const & p,
AsteroidList & Asteroids ) {
for ( AsteroidList::iterator iAst = Asteroids.begin();
iAst != Asteroids.end() ) {
if ( p.DistanceTo(&*iAst) <= iAst->getRadius() ) {
iAst = Asteroids.erase( iAst );
return ( true );
} else {
++iAst;
}
}
return ( false );
}

and then:

for ( iProj = Projectiles.begin(); iProj != Projectiles.end() ) {
if ( hits_asteroid( *iProj, Asteroids ) ) {
iProj = Projectiles.erase( iProj );
} else {
++ iProj;
}
}


If you want to fold that into a double loop (e.g., if you don't like
predicates with side effects), I would think that the best way is to have a
boolean flag that keeps track whether an explosion has happened.

Just for others who might have had the same problems:

I implemented the version with the boolean "explode" flag, but that one
seemed too complex, so I thought about it again and came up with a new
solution which, IMO, is the best so far:

All my Objects get new member functions setToBeDeleted() and
isToBeDeleted() and I defined a predicate

bool isToBeDeleted(cSpaceObject& obj)
{
return obj.isToBeDeleted();
}

so that now the loop looks like this:

for (iProj = Projectiles.begin(); iProj != Projectiles.end(); iProj++)
for (iAst = Asteroids.begin(); iAst != Asteroids.end(); iAst++)
if (iProj->DistanceTo(&*iAst) <= iAst->getRadius())
{
iAst->setToBeDeleted();
iProj->setToBeDeleted();
}
Asteroids.remove_if(isToBeDeleted);
Projectiles.remove_if(isToBeDeleted);

Thanks again for all the constructive input.

Regards
Philip

 

[Kai-Uwe Bux]

Just for others who might have had the same problems:

I implemented the version with the boolean "explode" flag, but that one
seemed too complex, so I thought about it again and came up with a new
solution which, IMO, is the best so far:

All my Objects get new member functions setToBeDeleted() and
isToBeDeleted() and I defined a predicate

bool isToBeDeleted(cSpaceObject& obj)
{
return obj.isToBeDeleted();
}

so that now the loop looks like this:

for (iProj = Projectiles.begin(); iProj != Projectiles.end(); iProj++)
for (iAst = Asteroids.begin(); iAst != Asteroids.end(); iAst++)
if (iProj->DistanceTo(&*iAst) <= iAst->getRadius())
{
iAst->setToBeDeleted();
iProj->setToBeDeleted();
}
Asteroids.remove_if(isToBeDeleted);
Projectiles.remove_if(isToBeDeleted);

Thanks again for all the constructive input.

Note that this has different semantics: in this version, one projectile can
take out several asteroids and an asteroid can be hit by several
projectiles.


Best

Kai-Uwe Bux