std::list traversal+erase

[Frank Neuhaus]

Hi
I have some std list, I'd like to traverse. During the traversal, I want to
conditionally delete some objects.

My code for that is like this right now:

for (std::list<myStruct>::iterator it=myList.begin();it!=myList.end()
{
if (it->someCondition)
{
std::list<myStruct>::iterator it2=it;
++it;
myList.erase(it2);
continue;
}

// .. do some work on the myStructs that arent supposed to be deleted
yet...

++it;
}

Is there any more elegant solution for my problem? It's quite ugly code
right now imho.
Simply using myList.erase(it++); doesnt work because after the erase line,
the iterator isnt valid anymore and thus cant be increased anymore.

Thanks alot

 

[Rolf Magnus]

Hi
I have some std list, I'd like to traverse. During the traversal, I want
to conditionally delete some objects.

My code for that is like this right now:

for (std::list<myStruct>::iterator it=myList.begin();it!=myList.end()
{
if (it->someCondition)
{
std::list<myStruct>::iterator it2=it;
++it;
myList.erase(it2);
continue;
}

// .. do some work on the myStructs that arent supposed to be deleted
yet...

++it;
}

Is there any more elegant solution for my problem? It's quite ugly code
right now imho.
Simply using myList.erase(it++); doesnt work because after the erase line,
the iterator isnt valid anymore and thus cant be increased anymore.

Just use the returned iterator:

if (it->someCondition)
{
it = myList.erase(it);
}
else
{
//do the work
++it;
}

 

[peter koch]

Hi
I have some std list, I'd like to traverse. During the traversal, I want to
conditionally delete some objects.

Are you sure you want to use a list? std::vector (or std::deque) might
well be a better choice here.

My code for that is like this right now:

for (std::list<myStruct>::iterator it=myList.begin();it!=myList.end()
{
if (it->someCondition)
{
std::list<myStruct>::iterator it2=it;
++it;
myList.erase(it2);
continue;
}

Replace with:
if (it->someCondition)
{
myList.erase(it++);
}
else
++it;

// .. do some work on the myStructs that arent supposed to be deleted
yet...

++it;
}

Is there any more elegant solution for my problem? It's quite ugly code
right now imho.
Simply using myList.erase(it++); doesnt work because after the erase line,
the iterator isnt valid anymore and thus cant be increased anymore.

That is not correct. it++ is similar to (pseudocode):

iterator increment(iterator& i)
{
iterator res = i;
i = i + 1;
return res;
}

so in myList.erase(it++), the iterator is incremented before
myList.erase is called.

/Peter

 

[Duane Hebert]

Are you sure you want to use a list? std::vector (or std::deque) might
well be a better choice here.

Are you sure that you want to recommend a vector
when he's erasing elements like this? Seems
to me that a list is a better choice given that.

The post increment on erase else pre increment
idiom won't work on a vector.

 

[Frank Neuhaus]

Is there any more elegant solution for my problem? It's quite ugly code

Just use the returned iterator:

if (it->someCondition)
{
it = myList.erase(it);
}
else
{
//do the work
++it;
}

Mh I guess thats what I've been looking for - thanks

 

[Frank Neuhaus]

Are you sure you want to use a list? std::vector (or std::deque) might

well be a better choice here.

Definately. As Duane said - deleting random objects from a container sounds
alot like a case for lists to me

That is not correct. it++ is similar to (pseudocode):

iterator increment(iterator& i)
{
iterator res = i;
i = i + 1;
return res;
}

so in myList.erase(it++), the iterator is incremented before
myList.erase is called.

Mh ... I just tried it and it worked this time. Though I am sure I've
experienced problems with this in the past - can't reproduce them right now
though :/

 

[mohammad.nabil.h]

Hi
I have some std list, I'd like to traverse. During the traversal, I want to
conditionally delete some objects.

My code for that is like this right now:

for (std::list<myStruct>::iterator it=myList.begin();it!=myList.end()
{
if (it->someCondition)
{
std::list<myStruct>::iterator it2=it;
++it;
myList.erase(it2);
continue;
}

// .. do some work on the myStructs that arent supposed to be deleted
yet...

++it;

}Is there any more elegant solution for my problem? It's quite ugly code
right now imho.
Simply using myList.erase(it++); doesnt work because after the erase line,
the iterator isnt valid anymore and thus cant be increased anymore.

Thanks alot

You can use a combination of remove_if() and transform():
Just define:
bool cond_remove(myStruct m) { if(m.someCondition) return true; return
false; }
myStruct change(myStruct m) { do somework on m; return m; }

Then you do :
remove_if(myList.begin(), myList.end(),cond_remove);
transform(myList.begin(), myList.end(),myList.begin(), change);

 

[Frank Neuhaus]

You can use a combination of remove_if() and transform():

Just define:
bool cond_remove(myStruct m) { if(m.someCondition) return true; return
false; }
myStruct change(myStruct m) { do somework on m; return m; }

Then you do :
remove_if(myList.begin(), myList.end(),cond_remove);
transform(myList.begin(), myList.end(),myList.begin(), change);

Mh thats a nice method if you only want to remove certain elements, but as I
indicated in my original source code, I also want to do work on the non
deleted elements. So I'd need to traverse my list which is certainly not
that nice :/

 

[mohammad.nabil.h]

Mh thats a nice method if you only want to remove certain elements, but as I
indicated in my original source code, I also want to do work on the non
deleted elements. So I'd need to traverse my list which is certainly not
that nice :/

The remove_if() removes the elements you want to delete, the
transform() do what you want on the rest, which is the "non deleted
elements". I am not sure if I got your point of view right.

 

[Frank Neuhaus]

The remove_if() removes the elements you want to delete, the
transform() do what you want on the rest, which is the "non deleted
elements". I am not sure if I got your point of view right.

Ya but it still traverses the list twice, which is a performance hit I dont
want to take for this application.

 

[peter koch]

Are you sure that you want to recommend a vector
when he's erasing elements like this? Seems
to me that a list is a better choice given that.

Well... yes and no. Depending on the objects, that might be huge and
very expensive to copy, it might well be better to use a list. But
considering that you have to traverse the entire structure anyway, both
algorithms are O(n) and vector does have the added benefit that
elements lie nicely arranged for the CPU I'd expect std::vector to be
faster on "most" occasions.

/Peter

 

[peter koch]

Definately. As Duane said - deleting random objects from a container sounds
alot like a case for lists to me

If you erase the elements one at a time, you'd be correct. What I had
in mind was using vector::erase after calling std::remove_if. Try it -
I guess that one will be faster.

/Peter
[snip]

 

[Duane Hebert]

If you erase the elements one at a time, you'd be correct. What I had
in mind was using vector::erase after calling std::remove_if. Try it -
I guess that one will be faster.

The erase/remove_if idiom should be fine but the OP
wants to traverse the list and either erase something
or do some work with it. Given this requirement,
I would use a list. Of course, if this is proven to
be a bottleneck...

Our group has had this argument before about
always using vectors instead of lists. In cases
where there are inserts/deletes in the middle, benchmarking
has shown that the list is a better choice and the code
to handle this is simpler and more intuitive.

I've also seen cases where a list was a better choice
than a vector if the container was resized often
and there was no advance indication of the size
(basically making reserve impossible.) In cases
where we didn't need random access and weren't
able to reserve a size, a list actually performed
better than a vector with many unreserved push_back
calls. The list is going to use more memory but
it's likely going to cause less fragmentation, less
copying etc.

This is likely to be an implementation thing
though and dependant on how a compiler
can optimize your code. I think the basic
data structure guidelines for using a list
or vector (array) still apply for the most
part though.

 

[Kai-Uwe Bux]

Ya but it still traverses the list twice, which is a performance hit I
dont want to take for this application.

Beware: if you do it in one pass, you are more or less bound to use
std::list as your container (because of iterator invalidation issues). The
two pass approach would allow you to try out other containers. The choice
of the container is likely to have a much bigger impact on the performance
than the one/two pass alternative (for instance because it can affect cache
missed quite dramatically). Thus, you might be missing out on much bigger
gains by chasing a small improvement in the traversal of the sequence.


Best

Kai-Uwe Bux

 

[mohammad.nabil.h]

want to take for this application.

You can do it on one pass like this:

bool cond_remove(myStruct m) { if(m.someCondition) return true; do work
you want; return
false; }

 

[peter koch]

The erase/remove_if idiom should be fine but the OP
wants to traverse the list and either erase something
or do some work with it. Given this requirement,
I would use a list. Of course, if this is proven to
be a bottleneck...

I only now realise that work has to be done on the elements that should
not be deleted. You could do that with remove_if, but that makes it
somewhat of a kludge (in my opinion). And you should always code for
clarity until your profiler tells you otherwise.

What option is fastest still is unlclear. Basically it will depend of
the size of the container and what else is done with it. In the
"normal" case, my guess is that less than 200 elements a std::vector
will be optimal no matter what. But really you should not care to much
before profiling.

/Peter
[snip]

 

[Duane Hebert]

I only now realise that work has to be done on the elements that should
not be deleted. You could do that with remove_if, but that makes it
somewhat of a kludge (in my opinion). And you should always code for
clarity until your profiler tells you otherwise.

Absolutely. Profiling may not even show this as a bottleneck
to begin with.

What option is fastest still is unlclear. Basically it will depend of
the size of the container and what else is done with it. In the
"normal" case, my guess is that less than 200 elements a std::vector
will be optimal no matter what. But really you should not care to much
before profiling.

I think it depends a lot on the platform and
the compiler. I would tend to design based on
the general rules of which container to use,
and, as you say, for clarity.

If the application requires it, profile it and
then look for "unique" solutions based on
where the problem is.

Attempts at early optimization often have
the affect of making code less clear, harder to
maintain and not always more optimal.