Removing elements in a list that are also in another list

[Adam Hartshorne]

Hi All,

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.

Adam

[Victor Bazarov]

Adam Hartshorne wrote:

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'.

V

[Patrick Kowalzick]

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?

Regards,
Patrick

[Pete Becker]

Patrick Kowalzick wrote:

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)

[Victor Bazarov]

Patrick Kowalzick wrote:

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

[Patrick Kowalzick]

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?

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

[Patrick Kowalzick]

Hello Pete,

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

[Pete Becker]

Patrick Kowalzick wrote:

Hello Pete,

>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?).

No, remove as in remove from the list. We're dealing here with a
container, so we're not limited to the thngs you can do with a sequence.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)