Archived

This topic is now archived and is closed to further replies.

Gaiiden

Erasing an iterator in a loop

Recommended Posts

typedef vector[int] nums;
typedef vector[int]::iterator num_handle;

// assume this is filled with random numbers
nums my_numbers;
for (num_handle iter=my_numbers.begin(); iter!=my_numbers.end(); ++iter)
    if (*iter == 5)
        my_numbers.erase(iter);
  
This code does not work as well as I intended. In fact it doesn't work at all I know I'm using a vector container in this example but I get the same result using a list container too. I guess erasing the current iterator breaks the pointer chain and when ++iter comes around it points to no where. I need a way to patch that up so I can delete iterators in a loop. Anyone? btw - the [] should be angle brackets I know but, you know... html tags and all... _________________________________________________________________ Drew Sikora A.K.A. Gaiiden ICQ #: 70449988 AOLIM: DarkPylat Blade Edge Software Staff Member, GDNet Public Relations, Game Institute 3-time Contributing author, Game Design Methods , Charles River Media Online column - Design Corner at Pixelate Unnoficial IGDA chat! [polaris.starchat.net -> #igda] NJ IGDA Chapter - NJ developers unite!! [Chapter Home | Chapter Forum] "Real programmers don't work from 9 to 5. If any real programmers are around at 9am it's because they were up all night." -Anon. "It's not the size of the source that matters, it's how you use it" - Self

Share this post


Link to post
Share on other sites
If I understand what you are trying to do then I can give you the solution I use.

Rather than (VB/Psuedo code)

For I = Start to Finish
If condition then Remove(I)
Next

use:

For I = Finish to Start Step -1
If condition then Remove(I)
Next

Basically you move backwards in the list, so that when you delete an item it only affects the items you have already passed.


[edited by - michalson on January 18, 2003 7:17:51 PM]

Share this post


Link to post
Share on other sites
Hmmm, I doubt that would work since you still use the iterator (which would now be invalid) to do the step backwards. Someone posted a good way of doing it (can''t remember who though) like this:

  
std::vector<int> my_numbers;
for (std::vector<int>::iterator next=my_numbers.begin(),iter=next++ ; iter!=my_numbers.end() ; iter=next++)
if (*iter == 5)
my_numbers.erase(iter);

this keeps next one step ahead, so it will always have a valid iterator.


Joanus D''Mentia
---------------
Surely 100,000 lemmings couldn''t possibly be wrong!!!

Share this post


Link to post
Share on other sites
Inserting or removing elements invalidates reference, pointers, and iterators that refer to the following elements. You must use an algorithm to do this. Try this:


std::vector< int >coll;
std::vector< int >::iterator pos;
std::list< int >mylist;
int value;

coll.erase(remove(coll.begin(), coll.end(), val), coll.end());
list.remove(bind2nd(equal_to< int >(), value));


hope this helps


-----------------------------
"There are ones that say they can and there are those who actually do."

"...u can not learn programming in a class, you have to learn it on your own."







[edited by - cMADsc on January 18, 2003 8:06:32 PM]

Share this post


Link to post
Share on other sites

for (num_handle iter=my_numbers.begin(); iter!=my_numbers.end(); )
if (*iter == 5)
iter = my_numbers.erase(iter);
else
++iter;



[edited by - niyaw on January 18, 2003 8:06:55 PM]

Share this post


Link to post
Share on other sites
You can use either the remove or remove_if algorithms to get rid of the elements you don''t want. They return an iterator to the end of the new sequence. You can use that return value with end() of your container to erase the remaining elements, which have already been copied. Check the documentation to see how the algorithms work.

The only problems I can see with this method is that you don''t have the opportunity to call the deconstructor on removed items, since all the algorithm does it overwrite "bad" values with the good ones.

Share this post


Link to post
Share on other sites
typedef vector[int] nums;
typedef vector[int]::iterator num_handle

nums my_numbers;
num_handle iter

for (iter=my_numbers.begin();iter!=my_numbers.end();iter++)
{
if(!my_numbers.empty())
{
if (*iter == 5)
{
my_numbers.erase(iter);
}
}
else
{
break;
}
}

Share this post


Link to post
Share on other sites
What about:

for (int i=my_numbers.size()-1,i>=0;i--)
{
if (my_numbers(i)==5)
my_numbers.erase(my_numbers.begin()+i);
}

I basically always use integers to loop through vectors. Is this a bad practice?

Edit: replaced angle braquets with parenthesis for my_numbers(i) because of html tags...

[edited by - Floating on January 18, 2003 10:56:50 PM]

Share this post


Link to post
Share on other sites
quote:
I basically always use integers to loop through vectors. Is this a bad practice?

There are lots of algorithms which solve exactly this sort of problem. If you're still writing your own loops it's likely you're making things deliberately difficult for yourself.

cMADsc has the answer. Read, lookup, learn.

[edited by - petewood on January 19, 2003 2:14:08 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Michalson
If I understand what you are trying to do then I can give you the solution I use.

Rather than (VB/Psuedo code)

For I = Start to Finish
If condition then Remove(I)
Next

use:

For I = Finish to Start Step -1
If condition then Remove(I)
Next

Basically you move backwards in the list, so that when you delete an item it only affects the items you have already passed.


[edited by - michalson on January 18, 2003 7:17:51 PM]


In VB that will throw an error. List have changed or something.

Share this post


Link to post
Share on other sites
quote:
Original post by petewood
If you''re still writing your own loops it''s likely you''re making things deliberately difficult for yourself.


if you''ve got a substantial amount of context data, throwing it around predicate class members and constructors might not be convenient. in my experience, the code with explicit loops might often be shorter than code using algorithms and predicate classes. of course, in many cases the opposite holds true.

Share this post


Link to post
Share on other sites
Your solution (as corrected by Niaw's his first post) will work, though the constant moves involved with keeping the vector contiguous will kill performance.

The one implied by Zipster

num_handle itor = remove( my_numbers.begin(), my_numbers.end(), 5 );
my_numbers.erase( itor, my_numbers.end() );
is the canonical solution... though it will break with a container of pointers (memory leak).

Zipster - there shouldn't be a destructor problem : when you have a destructor, you must have an assignment operator that takes care of the overwriting.




[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]


[edited by - Fruny on January 19, 2003 2:57:02 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Fruny
Your solution ... will work, though the constant moves involved with keeping the vector contiguous will kill performance.


how does using std::remove improve the picture? it still moves all container elements.

Share this post


Link to post
Share on other sites
That''s really weird, I do the same thing in a game of breakout I wrote and it works just great. I just remove arbitrary parts of the vector though. Here''s what I did, and it works well.

  
void ball::collided_block(Level *level)
{
for(std::vector<TexQuad>::iterator it = level->area.begin(); it != level->area.end(); ++it)
{
TexQuad &temp = *it;
double right = temp.Point2.x;
double left = temp.Point1.x;
double top = temp.Point3.y;
double bottom = temp.Point1.y;

if(current_direction.x < 0 &&
current_position_x - velocity > left &&
current_position_x - velocity < right &&
current_position_y - radius < top &&
current_position_y - radius >= bottom)
{
reflect(1, 0);
it->hits--;
if(it->hits == 0)
level->area.erase(it);
break;
}

else if(current_direction.x > 0 &&
current_position_x + radius + radius + velocity > left &&
current_position_x + radius + radius + velocity < right &&
current_position_y - radius < top &&
current_position_y - radius >= bottom)
{
reflect(-1, 0);
it->hits--;
if(it->hits == 0)
level->area.erase(it);
break;
}

if(current_direction.y > 0 &&
current_position_y + velocity > bottom &&
current_position_y + velocity < top &&
current_position_x + radius < right &&
current_position_x + radius >= left)
{
reflect(0, -1);
it->hits--;
if(it->hits == 0)
level->area.erase(it);
break;
}

else if(current_direction.y < 0 &&
current_position_y - radius - radius - velocity > bottom &&
current_position_y - radius - radius - velocity < top &&
current_position_x + radius < right &&
current_position_x + radius >= left)
{
reflect(0, 1);
it->hits--;
if(it->hits == 0)
level->area.erase(it);
break;
}
}
}

I can''t really see any difference between them, so I''m at a loss.

Share this post


Link to post
Share on other sites
When you call erase on a single element, it remove it then shifts all the subsequent ones one position - all N of them.

i.e. if I erase B and E

    
A B C D E F G H I (end)
^
A B C D E F G H I (end)
^
A C D E F G H I (end) --- moved elements C through I
^
A C D E F G H I (end)
^
A C D E F G H I (end)
^
A C D F G H I (end) --- moved elements F through I
^
A C D F G H I (end)
^
A C D F G H I (end)
^
A C D F G H I (end)
^


remove usually works by overwriting the elements to remove with the ones that follow, keeping track of two iterators, one that reads, one that writes.


    
.
A B C D E F G H I (end)
^
.
A B C D E F G H I (end)
^
.
A C C D E F G H I (end) --- moved C
^
.
A C D D E F G H I (end) --- moved D
^
.
A C D D E F G H I (end)
^
.
A C D F E F G H I (end) --- moved F
^
.
A C D F G F G H I (end) --- moved G
^
.
A C D F G H G H I (end) --- moved H
^
.
A C D F G H I H I (end) --- moved I
^
.
A C D F G H I H I (end)
^

An iterator pointing to H will be returned and passed to erase, which will happily take off the last two elements... and there are no further elements to shift over.

Asymptotic worst-case run-time
erase in a loop : O( Ntotal*Nto erase)
erase/remove : O( Ntotal )


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]


[edited by - Fruny on January 19, 2003 3:28:28 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Tazel
Wow, Gaiiden, a GDNet Staff member asking a question. I thought gods didn''t hang out with the lesser people.


Heh - quite true there Tazel. However I don''t consider myself so high and mighty that I can''t humble myself in turning to a great resource when in need of some help.

Thanks for all the responses guys, I definetly have a better idea of what to do now.

Share this post


Link to post
Share on other sites
quote:
Zipster - there shouldn''t be a destructor problem : when you have a destructor, you must have an assignment operator that takes care of the overwriting.

Well technically the assignment wouldn''t call the destructor on the overwritten object, but with a properly written assignment operator, I guess it doesn''t matter, heh

Share this post


Link to post
Share on other sites
I have an idea:


  
void test()
{
std::vector<int> v;
v.push_back(0);
v.push_back(5);
v.push_back(2);
v.push_back(3);
v.push_back(5);
std::vector<int>::iterator i;

i = v.begin();
while(i != v.end())
if(*i == 5)
v.erase(i);
else
i++;

for(int j = 0; j < v.size(); j++)
printf("%d ", v[j]);
printf("\n");
}



Works on my computer.

Share this post


Link to post
Share on other sites
And with std::list



    
void test()
{
std::list<int> c;
c.push_back(0);
c.push_back(5);
c.push_back(2);
c.push_back(3);
c.push_back(5);
std::list<int>::iterator i;
i = c.begin();
while(i != c.end())
if(*i == 5)
i = c.erase(i); // THIS LINE IS DIFFERENT

else
i++;
for(i = c.begin(); i != c.end(); i++)
printf("%d ", *i);
printf("\n");
}




EDIT: Oops, the same thing already posted by niyaw.



[edited by - Advanced Bug on January 21, 2003 8:23:45 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by niyaw
if you''ve got a substantial amount of context data, throwing it around predicate class members and constructors might not be convenient.

That''s because C++ is bad at carrying around context, and so is bad at functional programming style.

Share this post


Link to post
Share on other sites
quote:
Original post by niyaw : if you've got a substantial amount of context data, throwing it around predicate class members and constructors might not be convenient.

Original post by SabreMan : That's because C++ is bad at carrying around context, and so is bad at functional programming style.

Original post by niyaw : and your suggested way of dealing with it, if any, would be?


Looking at the 'context' that you're talking about, I assume you mean that there are a lot of variables in the function body and they are visible in the loop and made use of. You're saying that moving the operations that the loop performs into a seperate function isn't possible because of all the context that is needed.

There are so many ways to deal with this I'll just note a few different possibilties.

1) replace variables with functions ie instead of x = getX(); where x is then important in the loop, just use getX(). Then when the loop code is extracted to a new function it will have access to getX().

2) pass the context to the function as a series of parameters

3) clump the context together to make an object and pass that. If a set of data is important in the loop it may be that it belongs together.

4) copy the whole function and make it into an object. Make the local, context variables into members.

Of course not all of these are without their side-effects, but they're good starting points.

There are many other ways to improve code. I'll try and think of more if you wish. I'm at home with flu so am hanging out all day but being quite sluggish and grouchy too.

[edited by - petewood on January 21, 2003 10:03:10 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by niyaw
and your suggested way of dealing with it, if any, would be?

Well, I might suggest not using languages which unnecessarily limit expressivity, but that would probably upset people. So I won''t.

Share this post


Link to post
Share on other sites
quote:
Well, I might suggest not using languages which unnecessarily limit expressivity, but that would probably upset people. So I won't.

I'm learning LISP because of you. Really nice, I can see where c++ template meta-programming found all it's ideas.

[edited by - petewood on January 21, 2003 11:37:49 AM]

Share this post


Link to post
Share on other sites