473,223 Members | 1,790 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,223 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 3547
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...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

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.