Sign in to follow this  
obhi

Removing from a list while iterating.

Recommended Posts

suppose i'm iterating over objects stored in a array and calling functions over the objects. now the object asks to get deleted from this array and it informs he class holding this array. the class has to comply, but since it is processing the object array it cannot directly delete from this array. My problem is i want to delete this object from this array while processing (storing it to later delete it wont do because the object is getting killed after its request) and i cannot use reference counting either. any suggestions how t do it or which data structure to use. Eg code: void Holder::Iterateover() { for each object in objectarray object->CallMe() } void Holder::Deleteobject(object) { remove object from objectarray } void KillerObject::CallMe() { Holder::Deleteobject(this) } this might be very trivial, i tried quite a few solutions but somehow it is not working (and my engine is crashing.) last bit of info - the 'objectarray' in question is rather sorted and we want it that way. thanks in advance.

Share this post


Link to post
Share on other sites
I can't explain it in words, so here's some code:


bool KillerObject::CallMe()
{
// Holder::Deleteobject(this);
return true; // return true on removal
}

for ( std::list<KillerObject>::iteartor it = thelist.begin(), end = thelist.end(); it != end; /* no inc */ )
if ( (*it).CallMe() )
it = thelist.erase( it );
else
++it;





Also, having the elements know about its container is bad mojo, and should be avoided if possible.

EDIT:
Nice catch there, Ravyne :)

[Edited by - _fastcall on June 4, 2009 12:28:05 PM]

Share this post


Link to post
Share on other sites
_fastcall has it right, except that it should be "it = thelist.erase(it);" instead of "it = thelist.remove(it);"

The reason this happens is because the iterator becomes invalid after you've erased it (much the same way as a pointer becomes invalid after deleting the memory held by it) so you cannot get the next element from it. The erase(iterator) method returns an iterator to the next element, allowing you to continue. If the erased item was the last in the list, then the method returns an iterator to the end of the list.

For erasing a range of elements, there is a ranged erase, erase(iterator first, iterator last), which erases all elements between the two iterators, and whose return value behaves identically to erase(iterator).

Share this post


Link to post
Share on other sites
a note on the previous example if you want to continue through the list you should use a copy of the iterator then increment the original before deleting. If you remove the item the iterator points to the iterator is invalid. So do like the following:

list<foo> List;
list<foo>::iterator i = List.Begin();
list<foo>::iterator Delete;
while(i != List.end())
{
if((*i).DeleteCondition())
{
Delete = i;
i++;
List.erase(Delete);
continue;
}
i++;
}

Share this post


Link to post
Share on other sites
thanks for the reply's...but the function 'CallMe in this eg' isn't really something that returns true or false or info about if the object should continue exiting or not...anyway probably that is the best way around the problem because you dont end up keeping a dangling pointer alive.

Share this post


Link to post
Share on other sites

list<foo> List;
list<foo>::iterator i = List.Begin();
list<foo>::iterator DeleteIt;
while ( i != List.end() )
{
if ( (*i).DeleteCondition() )
{
DeleteIt = i;
i++;
List.erase( DeleteIt );
continue;
}
i++;
}



... refactors into:


for ( list<foo>::iterator it = list.begin(), end = list.end(); it != end; /* no increment */ )
if ( (*it).DeleteCondition() )
it = list.erase( it );
else
++it;



Use whatever you find more readable. [smile]

Share this post


Link to post
Share on other sites
Removing based on a condition is part of the standard library. Use it.

#include <algorithm>
#include <functional>
#include <list>

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(),
std::mem_fun_ref(&foo::deleteCondition)), L.end());
}

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Removing based on a condition is part of the standard library. Use it.

#include <algorithm>
#include <functional>
#include <list>

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(),
std::mem_fun_ref(&foo::deleteCondition)), L.end());
}


Just because someone put it in the library doesn't mean that it has to be used. I find the loop much more clear. It's also easier to modify in the future.

For instance, if the condition for deleting changes, I can do
for (list<foo>::iterator it = list.begin(), end = list.end(); it != end; /* no increment */ ) {
if ((*it).DeleteCondition() || AnotherCondition(*it))
it = list.erase( it );
else
++it;
}




Now let's say I want to log the event when one of these deletions happen:
for (list<foo>::iterator it = list.begin(), end = list.end(); it != end; /* no increment */ ) {
if ((*it).DeleteCondition() || AnotherCondition(*it)) {
log << "WARNING: Deleting foo " << *it << "\n";
it = list.erase( it );
}
else
++it;
}




Would you mind telling us what that would look like in the other style of coding?

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Would you mind telling us what that would look like in the other style of coding?

Sure.

bool condition(foo& f)
{
bool del = f.deleteCondition() || AnotherCondition(f));
if (del) log << "WARNING: Deleting foo " << f << "\n";
return del;
}

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(), condition), L.end());
}

Share this post


Link to post
Share on other sites
The problem here is how you've structured your code. Eith the structure you are using now is that you are removing the object from the list through another funciton while iterating the list.

There are several solitions to this:

- have the CallMe function return true/false if the object should live and then use one of the many posted loop examples here and delete the object based on that.

- another solution could be to mark the object as "remove me later" so you at least dont invalidate your container/iterators while doing the CallMe functions.
and then at the end of your frame/process/run funciton remove all objects fromt he list that is marked as deleted.

- copy the entire list and (assuming list holds pointers) and then just keep code as you have it.

Share this post


Link to post
Share on other sites
Quote:

Just because someone put it in the library doesn't mean that it has to be used. I find the loop much more clear. It's also easier to modify in the future.

Just to note, when using std::vector rather than linked lists, the std::remove_if free function is more efficient than calling erase inside a loop body.

However DevFred, there is a std::list::remove_if member function, which takes advantage of how cheap linked lists are to remove from.

This can be generalised (and specialised):

#include <list>
#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>

template<typename Container, typename Predicate>
void remove_and_erase(Container &c, const Predicate &p)
{
c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
}

template<typename T, typename Predicate>
void remove_and_erase(std::list<T> &c, const Predicate &p)
{
c.remove_if(p);
}

struct predicate
{
bool operator()( int x ) const { return x % 2 == 0; }
};

template<typename container>
void test()
{
int data[] = {1,2,3,4,5, 6};
container numbers(data, data + 5);

remove_and_erase(numbers, predicate());

std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}

int main()
{
test<std::vector<int> >();
test<std::list<int> >();
}



Makes you love and hate C++ [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
However DevFred, there is a std::list::remove_if member function, which takes advantage of how cheap linked lists are to remove from.

Awesome, I didn't know that. I never use linked lists.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Quote:
Original post by rip-off
However DevFred, there is a std::list::remove_if member function, which takes advantage of how cheap linked lists are to remove from.

Awesome, I didn't know that. I never use linked lists.

I rarely use them too. I'm pretty sure I picked that tip from someone here, probably SiCrane.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Quote:
Original post by alvaro
Would you mind telling us what that would look like in the other style of coding?

Sure.

bool condition(foo& f)
{
bool del = f.deleteCondition() || AnotherCondition(f));
if (del) log << "WARNING: Deleting foo " << f << "\n";
return del;
}

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(), condition), L.end());
}


Well, now you are forced to write a separate function, which will make the code harder to follow. You'll also have to somehow pass `log' and any other local variables that you may want to use. What if I may want to break out of the loop in some cases?
for (list<foo>::iterator it = list.begin(), end = list.end(); it != end; /* no increment */ ) {
if (TerminatingCondition(*it))
break;
if ((*it).DeleteCondition() || AnotherCondition(*it)) {
log << "WARNING: Deleting foo " << *it << "\n";
it = list.erase( it );
}
else
++it;
}

Share this post


Link to post
Share on other sites
I have to disagree alvaro, having a separate function makes it explicitly clear under what condition the item is to be removed, without being muddled by looping constructs and the context of surrounding code. Also, apply the correct version of remove_if ensures that the optimal method of removal is employed.

Also keep in mind that that conditional-determining function is likely usable in other portions of the code, so it can help eliminate redundancy as well.

Its easy to "just use a for loop" when that's what you're used to, but after using the predicate function based approach, it becomes second nature.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ravyne
after using the predicate function based approach, it becomes second nature.


Nah, that's for languages with lambda functions. That, plus using a predicate like that can only be as efficient or less efficient than a straight-up loop.

Share this post


Link to post
Share on other sites
Quote:
Original post by nullsquared
Quote:
Original post by Ravyne
after using the predicate function based approach, it becomes second nature.


Nah, that's for languages with lambda functions.


Languages that support lambda functions do certainly make this easier.

Quote:
That, plus using a predicate like that can only be as efficient or less efficient than a straight-up loop.


Of course, that presumes that the person writing that straight-up loop actually knows how to implement it correctly -- and we've already seen two issues that serve as evidence that that's not quite as easy as it would seem -- one of correctness and one of efficiency.

Share this post


Link to post
Share on other sites
Quote:
Original post by nullsquared

Nah, that's for languages with lambda functions. That, plus using a predicate like that can only be as efficient or less efficient than a straight-up loop.


These days, it will be several times faster since it will be executed concurrently. At least in just about every language, even if they aren't strictly about pure closures.

Quote:
Makes you love and hate C++


The only thing that C++ still has going for these days is "you don't pay for what you don't use". And templates are cooler than generics.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ravyne
Languages that support lambda functions do certainly make this easier.

C++0x supports lambdas:

void blah(std::list<foo>& L)
{
L.erase(std::remove_if(L.begin(), L.end(), [&](foo& f)
{
return f.deleteCondition() || anotherCondition(f);
}
), L.end());
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by nullsquared

Nah, that's for languages with lambda functions. That, plus using a predicate like that can only be as efficient or less efficient than a straight-up loop.


These days, it will be several times faster since it will be executed concurrently. At least in just about every language, even if they aren't strictly about pure closures.

Of course, because we're clearly not talking about C++ here, not at all.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ravyne
I have to disagree alvaro, having a separate function makes it explicitly clear under what condition the item is to be removed, without being muddled by looping constructs and the context of surrounding code. Also, apply the correct version of remove_if ensures that the optimal method of removal is employed.

You can't protect against bad programmers.

Quote:
Also keep in mind that that conditional-determining function is likely usable in other portions of the code, so it can help eliminate redundancy as well.

If this is the case, by all means put it in its own function, even if you use a loop. The test I apply is, "if you can give it a good name, make it a function."

Quote:
Its easy to "just use a for loop" when that's what you're used to, but after using the predicate function based approach, it becomes second nature.

I have known about these predicates for about seven years now, and I have had to read code that uses them on occasion. I don't think my brain is wired the right way for them. :)

Perhaps with decent support for lambda expressions I could change my mind. However, this seems to be a solution to a problem that doesn't exist: Writing loops isn't a difficult task and I don't need help with it. People that can't write loops can't do many other things that programming involves, and should probably not do it.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Writing loops isn't a difficult task and I don't need help with it.

OK, but loops make a program harder to read, because you go below the necessary level of abstraction. I don't want to say
Quote:

I want to have an iterator start at the beginning of a list, and while it is not one past the end of the list, check if some condition holds for the element which the iterator refers to, and if it does remove it, and then the iterator changes. Otherwise increase the iterator.

But rather
Quote:

I want to remove each element from a list for which some condition holds.

Programming is about direct expression of intent.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Quote:
Original post by alvaro
Writing loops isn't a difficult task and I don't need help with it.

OK, but loops make a program harder to read, because you go below the necessary level of abstraction. I don't want to say
Quote:

I want to have an iterator start at the beginning of a list, and while it is not one past the end of the list, check if some condition holds for the element which the iterator refers to, and if it does remove it, and then the iterator changes. Otherwise increase the iterator.

But rather
Quote:

I want to remove each element from a list for which some condition holds.

Programming is about direct expression of intent.


You almost hit the nail. You just missed the point where a programmer doesn't actually read his code aloud in plain English, unless he's talking to some non-programming audience or something of the kind.

And, oh, just for the record: if you wrote your second statement with the same attitude as your first, then it would sound more as such:
Quote:

I want to erase the range of iterators between the end of the list and whatever the algorithm remove_if() returns when passed in iterators for the beginning and ending of the list and a member function pointer to the delete condition.


This:

for (std::list<foo>::iterator i = list.begin(), end = list.end(); i != end; )
if (i->deleteCondition())
i = list.erase(i);
else
++i;



Is must easier to read and write than this:

list.erase(std::remove_if(list.begin(), list.end(),
std::mem_fun_ref(&foo::deleteCondition)), list.end());


Why? Because it's straight forward. Yeah, if you have an elitist attitude, it might be fun to show off how much of the SC++L algorithms you've memorized and how you can condense a loop into a single line. But then when you really think about it, you definitely don't gain anything by doing it that way, especially not readability.

Share this post


Link to post
Share on other sites
Quote:

Why? Because it's straight forward. Yeah, if you have an elitist attitude, it might be fun to show off how much of the SC++L algorithms you've memorized and how you can condense a loop into a single line. But then when you really think about it, you definitely don't gain anything by doing it that way, especially not readability.

Its called an idiom. C++ has lots of them, and not all of them are intuitive.

A loop is such a fundamental structure that you can't make any assumptions when you encounter one in code. You have to examine the logic to see what it does. And what it does may not match what the programmer hoped it would do.

Compare this to the standard algorithms, which express the intent of the programmer. There may still be bugs, but they might be easier to spot because the intent is clearer.

When I see each of the following, I can almost instantly recognise what the programmer wanted to happen:

for_each() -> loop over elements and do something to each
remove_if() -> remove elements that satisfy some condition
copy() -> copy elements somewhere
transform() -> copy and mutate each element
partition() -> divide the range based on some condition
sort() -> sort the range.


I find writing an remove_if, erase loop much easier than manually writing the loop, particularly because I already have such a remove_and_erase() helper function in one of my headers. All I need is to create the appropriate functor.

Share this post


Link to post
Share on other sites
Quote:
Original post by nullsquared
Why? Because it's straight forward. Yeah, if you have an elitist attitude, it might be fun to show off how much of the SC++L algorithms you've memorized and how you can condense a loop into a single line. But then when you really think about it, you definitely don't gain anything by doing it that way, especially not readability.


It depends. C++ notation is verbose at best, and can get ugly ("Hello, Boost").

But as far as functional concepts go, they are fairly straight-forward. If anything, my complaint is that they lack some fundamental concepts which are often required, yet cannot be trivially implemented. For example - to stop iterating when a condition is met.

Readability depends. I prefer functional notation since it makes it easier to determine the meaning.

list.erase(std::remove_if(blah.blah(), blah.meh(),

foo::meh_foo_baz(&foo::deleteCondition)), hihi.meh());


It has to do with principle of least surprise. Both for loop and iterators can be borked, but the number of unusual conditions that can be done is, in my experience, lesser with standard algorithms.

Even with for loop loop there is a lot of redundancy. There is next to no reason whatsoever for loop to use any other range than 0 to n-1 inclusive. So this ends up being written as:
for (int i = 0; i < n; i++) {
if (delete_condition(i)) delete(i);
}



But neither of these is more or less verbose. If anything, they are both effectively redundant.

For this reason, I've long ago accustomed myself to do something like this:
for_every(list, do_something);
The rest is hidden behind scenes, while the end-user code remains as direct as possible.

But again, most of C++ code carries next to no information, simply due to syntactic rules. So for me personally, the position of tokens and symbols is secondary to use of idioms. Well-understood concepts are those that improve clarity.

While I personally consider GoF patterns to be crude and frequently misused, I never ignore the productivity gains just they alone brought, let alone what improvements effective use of idioms can do.

A trivial example:
if (open_device(&f, "foo")} goto error;
if (read_char(f, &ch)) goto error;
if (read_int(f, &in)) goto error;
error:
if (close_file(f)) printf("Error closing file");


While some would squirm just at sight of goto, some will instantly recognize this as exception handling in C.

It's not tokens and syntax that determines clarity of code. It depends a lot on intended audience, purpose, as well as expected form.

A lot of C++ libraries are horribly verbose. That alone is not something that directly impacts readability.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this