473,325 Members | 2,860 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

std::list traversal+erase

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
Oct 7 '06 #1
16 3556
Frank Neuhaus wrote:
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;
}
Oct 7 '06 #2

Frank Neuhaus wrote:
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

Oct 7 '06 #3

"peter koch" <pe***************@gmail.comwrote in message
news:11**********************@m7g2000cwm.googlegro ups.com...
>
Frank Neuhaus wrote:
>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.
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.
Oct 7 '06 #4
>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;
}
Mh I guess thats what I've been looking for - thanks :-)
Oct 7 '06 #5
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 :/
Oct 7 '06 #6


On Oct 7, 6:17 pm, "Frank Neuhaus" <fneuh...@uni-koblenz.dewrote:
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);

Oct 7 '06 #7
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 :/
Oct 7 '06 #8

Frank Neuhaus wrote:
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 :/
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.

Oct 7 '06 #9
>
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.
Oct 8 '06 #10

Duane Hebert wrote:
"peter koch" <pe***************@gmail.comwrote in message
news:11**********************@m7g2000cwm.googlegro ups.com...

Frank Neuhaus wrote:
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.

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
>
The post increment on erase else pre increment
idiom won't work on a vector.
Oct 8 '06 #11

Frank Neuhaus wrote:
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 ;)
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]

Oct 8 '06 #12

"peter koch" <pe***************@gmail.comwrote in message
news:11********************@i42g2000cwa.googlegrou ps.com...
>
Frank Neuhaus wrote:
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 ;)
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.
Oct 8 '06 #13
Frank Neuhaus wrote:
>>
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.
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
Oct 8 '06 #14


On Oct 8, 1:22 am, "Frank Neuhaus" <fneuh...@uni-koblenz.dewrote:
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.
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; }

Oct 8 '06 #15

Duane Hebert wrote:
"peter koch" <pe***************@gmail.comwrote in message
news:11********************@i42g2000cwa.googlegrou ps.com...

Frank Neuhaus wrote:
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 ;)
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...
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]

Oct 8 '06 #16

"peter koch" <pe***************@gmail.comwrote in message
news:11**********************@k70g2000cwa.googlegr oups.com...
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.
Oct 8 '06 #17

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Martin Magnusson | last post by:
I know a similar question was recently posted here, but after trying the solutions in that thread I still have problems. list<int> the_list; the_list.push_back(1); the_list.push_back(2);...
2
by: s | last post by:
Here is a snippet of my code: <code> list< MyClass * >outgoing_pool; MyClass* GetWaitingObject(string freq) { MyClass *temp_ptr = NULL; list<MyClass*>::iterator i;
8
by: ma740988 | last post by:
Consider: # include <iostream> using std::cout; using std::cin; using std::endl; # include <list> using std::list;
11
by: William Payne | last post by:
Ok, in my program I have a std::list<Document*>, where Document is one of my own classes. I need to go through this list and check each item if it's ready for deletion. If it's not, skip to...
25
by: Markus Svilans | last post by:
Hi, There seems to be some functionality missing from the STL. I am iterating through a linked list (std::list) using a reverse iterator and attempting to erase certain items from the list. It...
3
by: Dalbosco J-F | last post by:
Hi, Sorry if this has already been answered. Given a std::list and a reverse_iterator is there a way to erase the element pointed to by the reverse_iterator via the erase method? Apparently...
5
by: Christopher | last post by:
The situation is that a std::list<std::set<std::string is being iterated through. Upon certain criteria some sets become empty. I need to remove the empty sets from the list. Is it safe to...
7
by: TBass | last post by:
So I have a class: class Client { unsigned int ClientID; .... }; class MyListenSocket
4
by: TBass | last post by:
Hi, I've got a class that uses a std::list to store tags that need to be written out to a device. I've had no problem with the lists in terms of iterating and reading values. My problem is when...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.