# Removing elements in a list that are also in another list

Discussion in 'C++' started by Adam Hartshorne, Jan 26, 2006.

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.

2. ### Victor BazarovGuest

> 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

Victor Bazarov, Jan 26, 2006

3. ### Patrick KowalzickGuest

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

Patrick Kowalzick, Jan 27, 2006
4. ### Pete BeckerGuest

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

Pete Becker, Jan 27, 2006
5. ### Victor BazarovGuest

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

Victor Bazarov, Jan 27, 2006
6. ### Patrick KowalzickGuest

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, Jan 27, 2006
7. ### Patrick KowalzickGuest

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

Patrick Kowalzick, Jan 27, 2006
8. ### Pete BeckerGuest

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

Pete Becker, Jan 27, 2006