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>::ite rator s_erase(list<ty pel, list<type>::ite rator 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<cShipShips ;
list<cProjectil eProjectiles;
list<cAsteroidA steroids;

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

Regards
Philip

[Christopher]

Re: stl::list modified erase

On Mar 17, 4:52 pm, Philip Mueller <m...@alienenpe ror.DELETETHIS. de>
wrote:

Hi,
>
I am using multiple stl::list s of different types.
>
Now I want to write a function
>
list<type>::ite rator s_erase(list<ty pel, list<type>::ite rator 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<cShipShips ;
list<cProjectil eProjectiles;
list<cAsteroidA steroids;
>
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::eras e
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]

Re: stl::list modified erase

On Mar 17, 5:54 pm, Christopher <cp...@austin.r r.comwrote:

On Mar 17, 4:52 pm, Philip Mueller <m...@alienenpe ror.DELETETHIS. de>
wrote:
>
>
>

Hi,

>

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

>

Now I want to write a function

>

list<type>::ite rator s_erase(list<ty pel, list<type>::ite rator 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<cShipShips ;
list<cProjectil eProjectiles;
list<cAsteroidA steroids;

>

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::eras e
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::eras e 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.

[Philip Mueller]

Re: stl::list modified erase

Kai-Uwe Bux wrote:

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]

Re: stl::list modified erase

Philip Mueller wrote:

Kai-Uwe Bux wrote:

>Sure. Define a function template:

[...]

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

template < typename ListType >
typename ListType::itera tor
s_erase ( ListType & the_list,
typename ListType::itera tor 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 );

>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 :-)

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


Best

Kai-Uwe Bux

[Philip Mueller]

Re: stl::list modified erase

Kai-Uwe Bux schrieb:

Philip Mueller wrote:
>

>Kai-Uwe Bux wrote:

>>Sure. Define a function template:

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

>Unfortunatel y 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 );

When I do this

list<intTest;
list<int>::iter ator 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::li st<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?

>>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 :-)

>
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<cShipShips ;
for (list<cShip>::i terator 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]

Re: stl::list modified erase

Philip Mueller wrote:

Kai-Uwe Bux schrieb:

>Philip Mueller wrote:
>>

>>Kai-Uwe Bux wrote:
>>>Sure. Define a function template:

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

>>Unfortunate ly 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 );

>
When I do this
>
list<intTest;
list<int>::iter ator 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::li st<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.

>>>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 :-)

>>
>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_objec t );

Regards
Philip
>
[1]:
list<cShipShips ;
for (list<cShip>::i terator 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.]

Re: stl::list modified erase

In article <649j10F29cg3lU 1@mid.uni-berlin.de>,
Philip Mueller <me@alienenpero r.DELETETHIS.de wrote:

Kai-Uwe Bux schrieb:

Philip Mueller wrote:

Kai-Uwe Bux wrote:
>Sure. Define a function template:

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

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 );

>
When I do this
>
list<intTest;
list<int>::iter ator 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::li st<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.

>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 :-)

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<cShipShips ;
for (list<cShip>::i terator 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]

Re: stl::list modified erase

Philip Mueller wrote:

Hi,
>
I am using multiple stl::list s of different types.
>
Now I want to write a function
>
list<type>::ite rator s_erase(list<ty pel, list<type>::ite rator 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<cShipShips ;
list<cProjectil eProjectiles;
list<cAsteroidA steroids;
>
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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Philip Mueller]

Re: stl::list modified erase

Kai-Uwe Bux wrote:

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.beg in(); iProj != Projectiles.end (); iProj++)
for (iAst = Asteroids.begin (); iAst != Asteroids.end() ; iAst++)
if (iProj->DistanceTo(&*i Ast) <= iAst->getRadius())
{
iProj = Projectiles.era se(iProj);
iAst = Asteroids.erase (iAst);
}

What I mean to do here is test two list of objects for collisions
between an element from the "Projectile s" 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.beg in(); iProj != Projectiles.end ();)
{
iAst = Asteroids.begin ();
while (iAst != Asteroids.end()
&& iProj->DistanceTo(&*i Ast) iAst->getRadius())
iAst++;
if (iAst != Asteroids.end() )
{
iAst = Asteroids.erase (iAst);
iProj = Projectiles.era se(iProj);
}
else
iProj++;
}

There has to be a better way.

[Kai-Uwe Bux]

Re: stl::list modified erase

Philip Mueller wrote:

Kai-Uwe Bux wrote:

>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.beg in(); iProj != Projectiles.end (); iProj++)
for (iAst = Asteroids.begin (); iAst != Asteroids.end() ; iAst++)
if (iProj->DistanceTo(&*i Ast) <= iAst->getRadius())
{
iProj = Projectiles.era se(iProj);
iAst = Asteroids.erase (iAst);
}
>
What I mean to do here is test two list of objects for collisions
between an element from the "Projectile s" 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::i terator 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.beg in(); iProj != Projectiles.end () ) {
if ( hits_asteroid( *iProj, Asteroids ) ) {
iProj = Projectiles.era se( 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]

Re: stl::list modified erase

Kai-Uwe Bux wrote:

Would this work:
>
bool hits_asteroid ( Projectile const & p,
AsteroidList & Asteroids ) {
for ( AsteroidList::i terator 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.beg in(); iProj != Projectiles.end () ) {
if ( hits_asteroid( *iProj, Asteroids ) ) {
iProj = Projectiles.era se( 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(c SpaceObject& obj)
{
return obj.isToBeDelet ed();
}

so that now the loop looks like this:

for (iProj = Projectiles.beg in(); iProj != Projectiles.end (); iProj++)
for (iAst = Asteroids.begin (); iAst != Asteroids.end() ; iAst++)
if (iProj->DistanceTo(&*i Ast) <= iAst->getRadius())
{
iAst->setToBeDeleted ();
iProj->setToBeDeleted ();
}
Asteroids.remov e_if(isToBeDele ted);
Projectiles.rem ove_if(isToBeDe leted);

Thanks again for all the constructive input.

Regards
Philip

[Kai-Uwe Bux]

Re: stl::list modified erase

Philip Mueller wrote:

Kai-Uwe Bux wrote:

>Would this work:
>>
> bool hits_asteroid ( Projectile const & p,
> AsteroidList & Asteroids ) {
> for ( AsteroidList::i terator 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.beg in(); iProj != Projectiles.end () ) {
> if ( hits_asteroid( *iProj, Asteroids ) ) {
> iProj = Projectiles.era se( 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(c SpaceObject& obj)
{
return obj.isToBeDelet ed();
}
>
so that now the loop looks like this:
>
for (iProj = Projectiles.beg in(); iProj != Projectiles.end (); iProj++)
for (iAst = Asteroids.begin (); iAst != Asteroids.end() ; iAst++)
if (iProj->DistanceTo(&*i Ast) <= iAst->getRadius())
{
iAst->setToBeDeleted ();
iProj->setToBeDeleted ();
}
Asteroids.remov e_if(isToBeDele ted);
Projectiles.rem ove_if(isToBeDe leted);
>
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