 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Patrick Kowalzick
Guest
|
 Posted: Fri Jan 27, 2006 10:10 am Post subject: Re: Removing elements in a list that are also in another lis |
 |
|
Hello Victor,
| Quote: | I was wondering if somebody could tell me if there is an efficient way to
do the following. Say I have a list(or vector) A and a list B, I want to
remove any elements in B, that are also elements in A.
Sort both lists and use 'set_difference'.
|
For set_difference you have to create a target list/vector. Do you know a
solution to remove the elements in B directly?
Regards,
Patrick
|
|
| Back to top |
|
 |
Pete Becker
Guest
|
| Posted: Fri Jan 27, 2006 2:14 pm Post subject: Re: Removing elements in a list that are also in another lis |
|
|
Patrick Kowalzick wrote:
| Quote: | Hello Victor,
I was wondering if somebody could tell me if there is an efficient way to
do the following. Say I have a list(or vector) A and a list B, I want to
remove any elements in B, that are also elements in A.
Sort both lists and use 'set_difference'.
For set_difference you have to create a target list/vector. Do you know a
solution to remove the elements in B directly?
|
Assuming you've already sorted the two lists, you do essentially what
set_difference does: start with the first element from the selector
list, and walk through the target list until you reach an element that
isn't less than that one. If it's equal, remove it and move to the next
element. Move to the next element in the selector list. Repeat until done.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
|
|
| Back to top |
|
|
Victor Bazarov
Guest
|
| Posted: Fri Jan 27, 2006 2:19 pm Post subject: Re: Removing elements in a list that are also in another lis |
|
|
Patrick Kowalzick wrote:
| Quote: | I was wondering if somebody could tell me if there is an efficient way to
do the following. Say I have a list(or vector) A and a list B, I want to
remove any elements in B, that are also elements in A.
Sort both lists and use 'set_difference'.
For set_difference you have to create a target list/vector. Do you know a
solution to remove the elements in B directly?
|
A solution would be to write your own "is_contained_in" predicate and then
run 'remove_if'. Something like
list_A.remove_if(is_contained_in(list_B));
That has O(n*m) complexity but without them both sorted it should suffice.
V
|
|
| Back to top |
|
|
Patrick Kowalzick
Guest
|
| Posted: Fri Jan 27, 2006 5:17 pm Post subject: Re: Removing elements in a list that are also in another lis |
|
|
Hello Victor,
| Quote: | I was wondering if somebody could tell me if there is an efficient way
to do the following. Say I have a list(or vector) A and a list B, I want
to remove any elements in B, that are also elements in A.
Sort both lists and use 'set_difference'.
For set_difference you have to create a target list/vector. Do you know a
solution to remove the elements in B directly?
A solution would be to write your own "is_contained_in" predicate and then
run 'remove_if'. Something like
list_A.remove_if(is_contained_in(list_B));
That has O(n*m) complexity but without them both sorted it should suffice.
|
Yes, this would be a solution for unsorted lists. For sorted lists it could
be more effective.
Thanks,
Patrick
|
|
| Back to top |
|
|
Patrick Kowalzick
Guest
|
| Posted: Fri Jan 27, 2006 5:22 pm Post subject: Re: Removing elements in a list that are also in another lis |
|
|
Hello Pete,
| Quote: | I was wondering if somebody could tell me if there is an efficient way
to do the following. Say I have a list(or vector) A and a list B, I want
to remove any elements in B, that are also elements in A.
Sort both lists and use 'set_difference'.
For set_difference you have to create a target list/vector. Do you know a
solution to remove the elements in B directly?
Assuming you've already sorted the two lists, you do essentially what
set_difference does: start with the first element from the selector list,
and walk through the target list until you reach an element that isn't
less than that one. If it's equal, remove it and move to the next element.
Move to the next element in the selector list. Repeat until done.
|
"remove" in the sense of the Standard Library (pushing non removed elements
as far to the front as possible?).
So we get something like:
iterator remove_set_difference( iterator,
iterator,const_iterator,const_iterator );
v.erase( v.remove_set_difference( v.begin(), v.end(), v2.begin(),
v1.begin() ), v.end() );
Regards,
Patrick
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
